Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


share|cite|improve this question
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. – jp26 Feb 18 '13 at 18:00
I have edited the ranges of some of the elements in your question. Please have a look to make sure everything is correct. – Paresh Feb 18 '13 at 18:08
Can you explain why it is necessary to have $3m$ copies of $C_4$? (my expansion works for any number) – jp26 Feb 18 '13 at 18:26
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)? – kim_kibun Feb 18 '13 at 20:24

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.