Open Collections

Distinguishing SierpiÅ ski products of graphs

Banff International Research Station for Mathematical Innovation and Discovery

The SierpiÅ ski product of graphs was introduced as a generalization of SierpiÅ ski graphs, which is a fractal-like family of graphs. The main building blocks of SierpiÅ ski graphs are complete graphs and each next iteration is built in the fractal-like manner of a complete graph. This idea was recently generalized to a graph product, where instead of initially taking just one graph, we build a fractal-like structure with two arbitrary graphs, say $G$ and $H$. Intuitively this is done in such a way that the product $G\otimes H$ has $|G|$ copies of graph $H$ which are connected among themselves according to the edges in $G$. So we get a graph with local structure of $H$, but global structure of $G$ (i.e., if we contract all copies of $H$ to a vertex, we get a copy of graph $G$). This construction is interesting because it may yield graphs with distinguishing number greater than 2. In the talk I will describe the SierpiÅ ski products and list some of their basic properties, which may be useful to answer the open question(s) about the distinguishing number of SierpiÅ ski products.

Mathematics; Combinatorics; Group theory and generalizations; Discrete mathematics

video/mp4

Author affiliation: Comenius University in Bratislava

2019-03-19

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/68913

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/