# How to draw Sierpinski 4-cycle graphs?

this is sierprinski 4 cycle graph S(1,C4), S(2,C4), S(3,C4).....and so on. I am trying to make but fail to make. so help me

• Welcome to TeX - LaTeX! Questions about how to draw specific graphics that just post an image of the desired result are really not reasonable questions to ask on the site. Please post a minimal compilable document showing that you've tried to produce the image and then people will be happy to help you with any specific problems you may have. See minimal working example (MWE) for what needs to go into such a document. – Andrew Swann Jun 10 '17 at 12:58
• Since you have tried something, edit your question and add your code, even if it is not working. – CarLaTeX Jun 10 '17 at 13:41

It's almost certainly the case that making the few of these you care about by using basic TikZ commands is the easiest thing to do. E.g., something like

\begin{tikzpicture}
\node[circle, draw, fill=black] (1) [label=south west:1] at (0,0) {};
\node[circle, draw, fill=black] (2) [label=north west:2] at (0,1) {};
\node[circle, draw, fill=black] (3) [label=north east:3] at (1,1) {};
\node[circle, draw, fill=black] (4) [label=south east:4] at (1,0) {};
\draw (1) -- (2) -- (3) -- (4) -- (1);
\end{tikzpicture}


But that's kind of boring. So let's do something a little more interesting.

First, generalized Sierpinski graphs are pretty neat but they don't really specify a distance between nodes. (By distance, I mean when drawing the graph, not minimum path length between two nodes.) Looking at the figure you provided (which I assume you copied from Gravier et al.), it looks like the four copies of S(k-1,C_4) that make up S(n, C_4) are separated by a distance of n-1. So let's go with that.

The recursive structure lends itself to a recursive solution. So what we'd like to do when drawing S(n, C_4) is the following.

1. Figure out how much to shift each of the four copies of S(n-1, C_4).
2. Determine where to place each label.
3. Draw each of the four S(n-1, C_4), shifted and labeled appropriately.
4. Connect the appropriate nodes in the four copies of S(n-1, C_4).

The first step isn't hard, per se, but does require solving a basic recurrence relation. I'm sure there's an easier way to solve this, but let w(n) be the width of S(n, C_4). Now based on the separation rule derived above, we have the recurrence w(n) = 2*w(n-1) + n - 1 and w(1) = 1.

We can solve this using any standard method (or cheat like I did and use Wolfram|Alpha) to get w(n) = 3*2^(n-1) - n - 1. This gives us the width, but what we really want is the shift amount s(n) = w(n-1) + n - 1. Solving this gives s(n) = 3*2^(n-2) - 1 for n > 1. For n = 1, let s(1) = 1. (For what it's worth, this gives A083329 shifted by 1).

The second step, label placement, is not specified, so I made the following choice: Each node is a word in {1,2,3,4}^n. E.g., S(4, C_4) has nodes 1111, 1112, 1113, 1114, 1121, ..., 4444. The nodes that deserve labels are those for which the (n-1)-symbols in its name agree. So for n > 1, S(n, C_4) will have 16 labeled nodes—four to a side—and S(1, C_4) will have all four nodes labeled. I took some liberties with placement where I thought they looked decent/didn't overlap with adjacent node labels.

The third step, drawing, is easy. Using the shift amount computed in step 1, draw 4 copies of S(n-1, C_4).

Finally, we need to connect some nodes between the 4 copies. But what nodes? Fortunately, this is specified in the definition of S(n, G) (for arbitrary G). For all edges (x,y) in G, we need to add edges (xy...y, yx...x).

Now I don't know TikZ very well, so I hope experts will suggest improvements to my code. To construct this, I used the graphs library and constructed a graph macro.

\usepackage{tikz}
\usetikzlibrary{graphs}

\makeatletter
\newcommand*\s@dup[2]{%
\ifnum\numexpr#1>\@ne
#2%
\s@dup{#1-\@ne}{#2}%
\fi
}
\def\s@compute@label#1#2{%
\ifx#2\relax
\def\s@temp{#1}
\edef\s@label{[label=\s@label@pos:\s@prefix]}%
\else
\def\s@temp{#2}%
\expandafter\s@check@label
\fi
}
\def\s@check@label#1{%
\ifx#1\relax
\edef\s@label{[label=\s@label@pos:\s@prefix]}%
\else\if#1\s@temp
\expandafter\expandafter\expandafter\s@check@label
\else
\expandafter\expandafter\expandafter\s@mismatch
\fi\fi
}
\def\s@mismatch#1\relax{%
\def\s@label{}%
}
\def\s@label@pos{%
south west% 11
\or west%       12
\or north%      13
\or south%      14
\or west%       21
\or north west% 22
\or north%      23
\or south%      24
\or south%      31
\or north%      32
\or north east% 33
\or east%       34
\or south%      41
\or north%      42
\or east%       43
\or south east% 44
\fi
}

\tikzgraphsset{
level/.store in=\s@level,
prefix/.store in=\s@prefix,
no placement,
level=1,
prefix={},
declare={sierpinski}{%
[/utils/exec={%
\ifnum\s@level=\z@
% Step 2: Figure out what to label.
\expandafter\s@compute@label\s@prefix\relax
\edef\subgraph{\s@prefix \s@label}%
\else
% Step 1: Compute the shift amount.
\ifnum\s@level=\@ne
\def\s@shift{1}%
\else
\pgfmathsetmacro\s@shift{3*pow(2,\s@level-2)-1}%
\fi
\count@=\s@level\relax
\edef\subgraph{%
% Step 3: Draw each of the four S(n-1, C_4) shifted appropriately.
sierpinski [level=\the\count@, prefix=\s@prefix1, /tikz/shift={(0,0)}];%
sierpinski [level=\the\count@, prefix=\s@prefix2, /tikz/shift={(0,\s@shift)}];%
sierpinski [level=\the\count@, prefix=\s@prefix3, /tikz/shift={(\s@shift,\s@shift)}];%
sierpinski [level=\the\count@, prefix=\s@prefix4, /tikz/shift={(\s@shift,0)}];%
% Step 4:  Connect edges.
\s@prefix1\s@dup\s@level2 -- \s@prefix2\s@dup\s@level1;% 12...2 -- 21...1
\s@prefix2\s@dup\s@level3 -- \s@prefix3\s@dup\s@level2;% 23...3 -- 32...2
\s@prefix3\s@dup\s@level4 -- \s@prefix4\s@dup\s@level3;% 34...4 -- 43...3
\s@prefix4\s@dup\s@level1 -- \s@prefix1\s@dup\s@level4;% 41...1 -- 14...4
}%
\fi
},%
parse/.expand once=\subgraph
]%
}
}
\makeatother


Now we just need to use it!

\begin{tikzpicture}
\graph [nodes={circle, minimum size=4pt, inner sep=0pt, fill, empty nodes}] {sierpinski [level=1]};
\end{tikzpicture}


You can change how the nodes are drawn by changing the \graph parameters. Changing the level parameter to sierpinski will produce S(level, C_4). Here are levels 2, 3, and 4.

S(4, C_4) is large, so I added the x and y parameters to tikzpicture to specify the size.

\begin{tikzpicture}[x=2em,y=2em]
\graph [nodes={circle, minimum size=4pt, inner sep=0pt, fill, empty nodes}] {sierpinski [level=4]};
\end{tikzpicture}


I didn't include the "Copy 1" text because that wasn't as interesting to me, but it shouldn't be difficult to do.