Graphoidally Independent Infinite Cactus

Document Type : Original paper

Authors

1 Department of Mathematics, Sri Venkateswara College, University of Delhi, Delhi, India

2 Adjunct Professor (Prof of Eminence), Department of Mathematics, Ramanujan College, University of Delhi, Delhi, India

Abstract

A graphoidal cover of a graph $G$ (not necessarily finite) is a collection $\psi$ of paths (not necessarily finite, not necessarily open) satisfying the following axioms: (GC-1) Every vertex of $G$ is an internal vertex of at most one path in $\psi$, and (GC-2) every edge of $G$ is in exactly one path in $\psi$. The pair $(G, \psi)$ is called a graphoidally covered graph and the paths in $\psi$ are called the $\psi$-edges of $G$. In a graphoidally covered graph $(G, \psi)$, two distinct vertices $u$ and $v$ are $\psi$-adjacent if they are the ends of an open $\psi$-edge. A graphoidally covered graph $(G, \psi)$ in which no two distinct vertices are $\psi$-adjacent is called $\psi$-independent and the graphoidal cover $\psi$ is called a totally disconnecting graphoidal cover of $G$. Further, a graph possessing a totally disconnecting graphoidal cover is called a graphoidally independent graph. The aim of this paper is to establish complete characterization of graphoidally independent infinite cactus.

Keywords

Main Subjects

References

[1] B.D. Acharya and P. Gupta, Domination in graphoidal covers of a graph, Discrete Math. 206 (1999), no. 1-3, 3–33.
https://doi.org/10.1016/S0012-365X(98)00389-6
[2] B.D. Acharya and P. Gupta, Further results on domination in graphoidally covered graphs, AKCE Int. J. Graphs. Combin. 4 (2007), no. 2, 127–138.
[3] B.D. Acharya, P. Gupta, and D. Jain, On graphs whose graphoidal domination number is one, AKCE Int. J. Graphs. Combin. 12 (2015), no. 2-3, 133–140.
https://doi.org/10.1016/j.akcej.2015.11.007
[4] B.D. Acharya and E. Sampathkumar, Graphoidal covers and graphoidal covering number of a graph, Indian J. Pure Appl. Math. 18 (1987), no. 10, 882–890.
[5] S. Arumugam, B.D. Acharya, and E. Sampathkumar, Graphoidal covers of a graph: a creative review, Proceedings of the National workshop on Graph Theory and its Applications, Manonmaniam Sundaranar University, Tirunelveli, Eds. S. Arumugam, BD Acharya and E. Sampathkumar, Tata McGraw Hill, 1996, pp. 1–28.
[6] S. Arumugam, P. Gupta, and R. Singh, Bounds on graphoidal length of a graph, Electro. Notes Discrete Math. 53 (2016), 113–122.
https://doi.org/10.1016/j.endm.2016.05.010
[7] S. Arumugam and C. Pakkiam, Graphoidal bipartite graphs, Graphs Combin. 10 (1994), no. 2, 305–310.
https://doi.org/10.1007/BF02986680
[8] S. Arumugam and C. Pakkiam, Graphs with unique minimum graphoidal cover, Indian J. Pure Appl. Math. 25 (1994), no. 11, 1147–1147.
[9] S. Arumugam, I. Rajasingh, and P.R.L. Pushpam, Graphs whose acyclic graphoidal covering number is one less than its maximum degree, Discrete Math. 240 (2001), no. 1-3, 231–237.
https://doi.org/10.1016/S0012-365X(00)00350-2
[10] S. Arumugam, I. Rajasingh, and P.R.L. Pushpam, A note on the graphoidal covering number of a graph, J. Discrete Math. Sci. Cryptogr. 5 (2002), no. 2, 145–150.
[11] S. Arumugam and J.S. Suseela, Acyclic graphoidal covers and path partitions in a graph, Discrete Math. 190 (1998), no. 1-3, 67–77.
https://doi.org/10.1016/S0012-365X(98)00032-6
[12] P. Gupta, M. Agarwal, and R. Singh, On graphoidal length of a tree in terms of its diameter, AKCE Int. J. Graphs Combn. 17 (2020), no. 3, 703–707.
https://doi.org/10.1016/j.akcej.2019.12.012
[13] P. Gupta and D. Jain, Graphoidally independent infinite graphs, AKCE Int. J. Graphs Combn. 18 (2021), no. 2, 95–100.
https://doi.org/10.1080/09728600.2021.1953946
[14] O. Ore, Theory of Graphs, Amer. Math. Soc. Colloq. Publ. ,38, Providence, 1962.
[15] C. Pakkiam and S. Arumugam, On the graphoidal covering number of a graph, Indian J. Pure Appl. Math. 20 (1989), no. 4, 330–333.
[16] I. Sahul Hamid and A. Anitha, On label graphoidal covering number-I, Trans. Comb. 1 (2012), no. 4, 25–33.
https://doi.org/10.22108/toc.2012.2271
[17] D.B. West, Introduction to Graph Theory, Prentice hall Upper Saddle River, 2001.
Communications in Combinatorics and Optimization
Volume 9, Issue 3
September 2024
Pages 413-423

Files

Share

How to cite

Statistics