Let there be $3m$ (where $m$ is any counting numbers and $m\ge{2}$) copies of $C_4$. we denote each copy of $C_4$ as $C_4(i),\quad 1\le i \le 3m $. Let $v_j(i)\in V(C_4(i)),\quad 1\le j \le 4$ be adjacent to a vertex $v_r(k)\in V(C_4(k)),\quad 1\le k\le 3m,\ 1\le r \le 4$ with $i\neq k$ and $r$ and $j$ may not be necessarily equal and no vertex other in $C_4(i)$ is adjacent to another vertex of $C_4(k)$. We denote this graph as $\Gamma_m$. Here is an example where $m=3$:

enter image description here

Is there another way to define this kind of graph?


  • 2
    $\begingroup$ Do you need more than an "cubic expansion" of a graph to make it 3-regular? This works in general for any graph, just replace every vertex of degree $k>3$ by a $k$-cycle. The graph you show is the cubic expansion of a 4-regular graph with 9 vertices, for instance. $\endgroup$ – jp26 Feb 18 '13 at 18:00
  • $\begingroup$ I have edited the ranges of some of the elements in your question. Please have a look to make sure everything is correct. $\endgroup$ – Paresh Feb 18 '13 at 18:08
  • $\begingroup$ Can you explain why it is necessary to have $3m$ copies of $C_4$? (my expansion works for any number) $\endgroup$ – jp26 Feb 18 '13 at 18:26
  • $\begingroup$ Thanks Sir @jp26 it's not really necessary. i just need 3m copies of $C_4$ for my research. Btw sir, do you know any graph theory books that have this kind of topic (graph expansion)? (aside from N. Bigg's book)? $\endgroup$ – kim_kibun Feb 18 '13 at 20:24

Your Answer

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

Browse other questions tagged or ask your own question.