1
$\begingroup$

Consider a symmetric or arc-transitive graph except the odd cycle. Then, is it true that the graph could be partitioned into distinct parts such that each part has equal number of vertices except for a few singleton parts(which consists of single vertex) and such that each vertex in each part is adjacent to some other vertex in every other part except the part in which it is(the vertices in a part are independent) and the number of parts is $\le\Delta+1$ where $\Delta$ is the maximum degree?

I think this should be true, as any the graph is both vertex and edge transitive, hence any edge as well as vertex must be equivalent under an automorphism, thus the partitions must also be equivalent. Is the fact true for graphs that are only vertex transitive and not necessarily symmetric or edge transitive? What about Cayley graphs? or, restrictively, Cayley graphs of abelian groups? Thanks beforehand.

Improve this question
$\endgroup$
11
  • $\begingroup$ "[...] such that each vertex in each part is adjacent to some other vertex in other part?". Do you mean that each vertex has a neighbor in all parts (but its own) or some part (but its own)? $\endgroup$
    – M. Winter
    Commented May 9, 2019 at 13:56
  • $\begingroup$ @M.Winter yes, I mean each vertex has a neighbour in each part but its own $\endgroup$
    – vidyarthi
    Commented May 9, 2019 at 14:49
  • $\begingroup$ Do you have any bounds on the number of single vertices? I think it is pretty easy to find such a decomposition if I can make arbitrarily many vertices single (make all of them single in the extreme case). $\endgroup$
    – M. Winter
    Commented May 9, 2019 at 14:54
  • $\begingroup$ @M.Winter yes, edited the question $\endgroup$
    – vidyarthi
    Commented May 9, 2019 at 14:56
  • 1
    $\begingroup$ No, consider the cycle graph $C_5$. Since $5$ is prime, there must be a singleton vertex, and there're two vertices not adjacent to it. $\endgroup$
    – LeechLattice
    Commented May 9, 2019 at 16:37

1 Answer 1

Reset to default
4
$\begingroup$

Every connected vertex-transitive graph on an even number of vertices has a perfect matching, and each vertex in a connected vertex-transitive graph on an odd number of vertices is missed by a matching that covers all remaining vertices, see here.

So, for the even number of vertices case, choose a perfect matching $(u_1,v_1),(u_2,v_2),...$ and partition the graph into parts $u$ and $v$.

For the odd number of vertices case, remove a vertex $a$ and choose a perfect matching $(u_1,v_1),(u_2,v_2),...$ of the remaining graph and partition the graph into parts $u$, $v$ and $a$.

EDIT: It's not possible if the classes are required to be independent:

Consider the symmetric non-bipartite cubic graph on 182 vertices. If a partition were possible, the size of the classes must be in the following list:

91+91
1+1+180
1+1+90+90
1+1+1+179

$91+91$ is impossible by non-bipartiteness.

$1+1+180$ and $1+1+1+179$ are impossible by bounding on the largest independent set (the size is $77$).

$1+1+90+90$ is impossible by checking non-bipartiteness of all $2$-vertex-removed subgraphs: none of the $2$-vertex-removed subgraphs are bipartite.

So such a partition does not exist.

Improve this answer
$\endgroup$
3
  • $\begingroup$ But, suppose I want independent partitions. That is each partition consists of independent vertices. Is that too possible? $\endgroup$
    – vidyarthi
    Commented May 9, 2019 at 12:03
  • 1
    $\begingroup$ @vidyarthi It's not possible. Consider the symmetric non-bipartite cubic graph on 182 vertices, it's not possible to satisfy the requirements by counting the size of each class. $\endgroup$
    – LeechLattice
    Commented May 10, 2019 at 8:14
  • 1
    $\begingroup$ thanks, I see it. This is because, if there were such a partition, the number of parts would exceed $4$, right(in fact it would be $5$). You may write it as a full answer, which I would accept $\endgroup$
    – vidyarthi
    Commented May 10, 2019 at 8:19

You must log in to answer this question.

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