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.

  • $\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 May 9 '19 at 13:56
  • $\begingroup$ @M.Winter yes, I mean each vertex has a neighbour in each part but its own $\endgroup$ – vidyarthi May 9 '19 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 May 9 '19 at 14:54
  • $\begingroup$ @M.Winter yes, edited the question $\endgroup$ – vidyarthi May 9 '19 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 May 9 '19 at 16:37

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$ 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.

| cite | improve this answer | |
  • $\begingroup$ But, suppose I want independent partitions. That is each partition consists of independent vertices. Is that too possible? $\endgroup$ – vidyarthi May 9 '19 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 May 10 '19 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 May 10 '19 at 8:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.