/ 
Graph-Maker-Other-19
/ Graph::Maker::SierpinskiTriangles

NAME

Graph::Maker::SierpinskiTriangles - create Sierpinski graph

SYNOPSIS

use Graph::Maker::SierpinskiTriangles;
$graph = Graph::Maker->new ('Sierpinski_triangles', N => 3);

DESCRIPTION

Graph::Maker::SierpinskiTriangles creates a Graph.pm graph of the Sierpinski triangles graph. This is graph vertices at the vertices of the unit triangles in the Sierpinski triangle order N, and graph edges along the sides of those unit triangles.

N=>0       N => 1           N => 2

  *           *                *
 / \         / \              / \
*---*       *---*            *---*
           / \ / \          / \ / \
          *---*---*        *---*---*
                          / \     / \
                         *---*   *---*
                        / \ / \ / \ / \
                       *---*---*---*---*

Vertex names are unspecified. (In the current code they are coordinates in this sort of grid, but don't rely on that.)

Graph N comprises 3 copies of graph N-1 arranged around an empty middle triangle, and corner vertices in common.

      *
     / \
    / G \          three copies,
   @-----@         common corner vertices "@",
  / \   / \        empty middle
 / G \ / G \
*-----@-----*

This vertex merging, and edges tripling with no merging, means

NumVertices(N) = 3*NumVertices(N-1) - 3
               = (3^N + 1) * 3/2
               = 3, 6, 15, 42, 123, 366, ...   (A067771)

NumEdges(N)    = 3^(N+1)
               = 3, 9, 27, 81, 243, 729, ...   (A000244)

An equivalent bottom-up definition is to take each vertical unit triangle (horizontal base, peak upwards), insert a new vertex into each edge, and add a cycle of edges around them, in the manner of N=0 becoming N=1.

             *              *
  unit      / \            / \       new vertices "@"
triangle   /   \    =>    @---@      subdividing edges,
          /     \        / \ / \     new cycle around them
         *-------*      *---@---*

The number of such unit triangles is 3^N just by the replications (top-down or bottom-up).

There are various enclosed regions other than such upwards unit triangles. Total number of interior regions follows from the top-down replications by 3 copies and a new middle,

NumRegions(N) = 3*NumRegions(N) + 1
              = (3^(N+1) - 1)/2
              = 1, 4, 13, 40, 121, 364, ...       (A003462)

The graph is planar by its construction, so the combination of vertices, edges and interior regions satisfy Euler's formula

NumVertices(N) + NumRegions(N) = NumEdges(N) + 1

The towers of Hanoi state graph (Graph::Maker::Hanoi) is related to the graph here by taking the inside of each upward unit triangle as a vertex, and put edges between those unit triangles which touch at corners.

FUNCTIONS

$graph = Graph::Maker->new('Sierpinski_triangles', key => value, ...)

The key/value parameters are

N           => integer
graph_maker => subr(key=>value) constructor, default Graph->new

Other parameters are passed to the constructor, either graph_maker or Graph->new().

If the graph is directed (the default) then edges are added both ways between vertices. Option undirected => 1 creates an undirected graph and for it there is a single edge between vertices.

FORMULAS

Wiener Index

HOUSE OF GRAPHS

House of Graphs entries for the folded hypercubes here include

https://hog.grinvin.org/ViewGraphInfo.action?id=1310 (etc)

 1374   N=0   3-cycle
36261   N=1

OEIS

Entries in Sloane's Online Encyclopedia of Integer Sequences related to the folded hypercube include

http://oeis.org/A011782 (etc)

A067771   num vertices
A000244   num edges
A003462   num interior regions

SEE ALSO

Graph::Maker, Graph::Maker::Hanoi

HOME PAGE

http://user42.tuxfamily.org/graph-maker-other/index.html

LICENSE

Copyright 2020, 2021 Kevin Ryde

This file is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.

This file is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with This file. If not, see http://www.gnu.org/licenses/.