Independence fractals of fractal graphs

Document Type : Research Paper

Authors

1 Department of Mathematics, M E S Mampad College, Malappuram, India

2 MPSTME, NMIMS University Mumbai, Mumbai, India

Abstract

For an ordered subset $W=\{w_{1}, w_{2},...,w_{k}\}$ of $V(G)$ and a vertex $v\in V$, the metric representation of $v$ with respect to $W$ is a $k$-vector, which is defined as $r(v/W)=\{d(v,w_{1}), d(v,w_{2}),...,d(v,w_{k})\}$. The set $W$ is called a resolving set for $G$ if $r(u/W)=r(v/W)$ implies that $u= v$ for all $u,v \in V(G)$. The minimum cardinality of a resolving set of $G$ is called the metric dimension of $G$. For two graphs $G$ and $H$, the lexicographic product  $G \wr H$ of $H$ by $G$ is obtained from $G$ by replacing each vertex of $G$ with a copy of $H$. A graph $G$ is considered fractal if a graph $\Gamma$ exists, with at least two vertices, such as $G\simeq \Gamma \wr G$. This paper intends to discuss the fractal graph of some graphs and corresponding independence fractals. Also, compare the independent fractals of the fractal graph G, fractal factor $\Gamma$ and $\Gamma \wr G$.

Keywords

[1] J.I. Brown, K. Dilcher and R.J. Nowakowski, Roots of independence polynomials of well covered graphs, J. Alg. Combin. 11 (2000), 197–210.
[2] J.I. Brown, C.A. Hickman and R.J. Nowakowski, The independence fractal of a graph, J. Combin. Theory, Ser. B 87 (2003), no. 2, 209–230.
[3] J.I. Brown, C.A. Hickman and R.J. Nowakowski, On the location of roots of independence polynomial, J. Alg. Combin. 19 (2004), 273–282.
[4] J.I. Brown, C.A. Hickman and R.J. Nowakowski, The k-fractal of a simplicial complex, Discrete Math. 285 (2004), 33–45.
[5] G. Chartrand, L. Eroh, M.A. Johnson and O.R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math. 105 (2000), no. 1, 99–113.
[6] F. Harary, Graph Theory, Addison-Wesley Publishing Company, Inc., Reading, Massachusetts, 1969.
[7] F. Harary and R.A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976), no. 2, 191–195.
[8] C. Hernando, M. Mora, I.M. Pelayo, C. Seara, J. Ceaceres and M.L. Puertas, On the metric dimension of some families of graphs, Electronic Notes Discrete Math. 22 (2005), 129–133.
[9] P. Ille and R. Woodrow, Fractal graphs, J. Graph Theory 91 (2019), no. 1, 53–72.
[10] P. Ille, A proof of a conjecture of Sabidussi on graphs Idempotent under the lexicographic product, Discrete Math. 309 (2009), 3518–3522.
[11] P. Ille and R Woodrow, Decomposition tree of a lexicographic product of binary structures, Discrete Math. 311 (2011), 2346–2358.
[12] P.J. Slater, Leaves of trees, Proc. 6th Southeastern Conf. Combinatorics, Graph Theory Computing, Congr.  14 (1975), no. 37, 549–559.
Volume 14, Issue 10
October 2023
Pages 239-246
  • Receive Date: 05 May 2022
  • Revise Date: 16 June 2022
  • Accept Date: 08 July 2022