0
$\begingroup$

Let $G=(V,E)$ be a simple, undirected graph, that is $V$ is a set and $E \subseteq [V]^2 = \{\{v,w\}: v,w \in V \land v\neq w\}$.

For $v\in V$ and $S\subseteq V$ we set $$N(v,S) = \{w\in S: \{v,w\} \in E\}.$$ Given a partition $\frak P$ of $V$ into $2$ non-empty sets, and a vertex $v\in V$, we denote by $[v]$ the unique member of $\frak P$ containing $v$, and by $\neg[v]$ the unique member of $\frak P$ not containing $v$.

A partition $\frak P$ of $V(G)$ into 2 sets is said to be nice if $N(v,[v])> N(v,\neg[v])$ for all $v\in V$, and we call it nasty if $N(v,[v])< N(v,\neg[v])$ for all $v\in V$.

For which $n\in\mathbb{N}$ is there a graph $G$ on $n$ vertices such that $G$ has both a nice partition ${\frak P}_1$ as well as a nasty partition ${\frak P}_2$?

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ I think we can do all even numbers $2k \geq 4$ by taking $k$ disjoint edges. The partition that takes one vertex from each edge is nasty as each vertex has 0 neighbours in its own part, and 1 in the other. But the partition that takes some edges in one part and the remaining edges in the other part is nice, because each vertex has 1 neighbour in its own part and 0 in the other. $\endgroup$
    – Gordon Royle
    Commented Jul 21, 2015 at 10:59
  • 1
    $\begingroup$ More generally, given examples on $n_1$ vertices and $n_2$ vertices you can find an example on $n_1 + n_2$ vertices by taking a vertex-disjoint union. So it remains only to check whether such graphs exist for small odd $n$. $\endgroup$
    – Ben Barber
    Commented Jul 21, 2015 at 13:02

2 Answers 2

Reset to default
3
$\begingroup$

Such a graph exists if and only if $n \geq 4$.

The inequality defining "nice" implies that each set in your partition has at least two elements. Thus we need $n \geq 4$.

If $n \geq 4$ is even, then let $G$ be $\frac{n}{2}$ disjoint $2$-paths. This idea is explained in Gordon Royle's comment: the partition taking one vertex from each $2$-path is nasty, and the partition putting some $2$-paths in one set and some in another is nice.

If $n \geq 4$ is odd, then let $G$ consist of $\frac{n-1}{2}$ disjoint $2$-paths plus a $3$-path. For a nasty partition, take one vertex from each $2$-path plus the degree-two vertex from the $3$-path. For a nice partition, take the $2$-paths in one set and the $3$-path in another.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Any bipartite graph has a nasty partition and any disconnected graph (no isolated vertices) has a nice partition... $\endgroup$
    – Gordon Royle
    Commented Jul 21, 2015 at 15:46
  • $\begingroup$ @GordonRoyle: Yes, that's a very succinct way of expressing the main idea here. $\endgroup$
    – Will Brian
    Commented Jul 21, 2015 at 15:57
  • 1
    $\begingroup$ What if we ask for connected graphs with both types of partition? $\endgroup$
    – Gordon Royle
    Commented Jul 21, 2015 at 20:48
  • $\begingroup$ @GordonRoyle: Good question! This happens if and only if $n \geq 6$. To see that we need $n \geq 6$, suppose we have a "nice" partition of a graph on $4$ or $5$ vertices. We've already seen that nice partitions have at least two vertices in each partition set, so one set must have exactly two. To achieve niceness, there must be an edge between them and no edge to any vertex of the other partition piece. But then we lose connectedness, so we need $n \geq 6$. To see that $n \geq 6$ suffices, we only have to consider $n = 6,7$ (Ben Barber's answer does the rest). $\endgroup$
    – Will Brian
    Commented Jul 21, 2015 at 21:29
  • $\begingroup$ For $n = 6$, take the tree on vertices a,b,c,d,e,f with: a-c, b-c, c-d, d-e, d-f. Then $\{a,b,c\}$ is one half of a nasty partition, and $\{a,b,c\}$ is one half of a nice partition. By adding another vertex g with f-g, you can get a $7$-vertex graph that works. $\endgroup$
    – Will Brian
    Commented Jul 21, 2015 at 21:33
4
$\begingroup$

These graphs exist for every $n \geq 8$. They might exist for smaller $n$.

Start with a path $P$ on $n$ vertices. The bipartition of $P$ is certainly unfriendly. Let $e$ be an edge of $P$ that is as central as possible, and let the second partition be that with $e$ as the only cross edge. This is almost friendly, in that the only vertices the condition fails for are the endpoints of $e$.

To fix these vertices we add two new edges, each connecting one of the endpoints of $e$ to the vertex at distance two along $P$ away from $e$ (which is possible provided that $n \geq 6$). Then the second partition is friendly. Looking back at the original bipartition of $P$, these two new edges are internal to the parts. But provided $n \geq 8$, the endpoints of the new edges each had two edges across the bipartition originally, so they still have more neighbours in the other part than in their own.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .