Volume 4 • Issue 1 • PP: 01–04 • 2024
The Basis Number of Connected Vertex-Disjoint Graphs
Open Access & Copyright
© 2024 The Author(s). Published by ASPG. This article is licensed under the Creative Commons Attribution 4.0 International License (CC BY 4.0).
View PDF Abstract
The basis number b(G) of a graph G is defined to be the smallest positive integer k such that G has a k-fold basis for its cycle space. We seek an upper bound for b(G1 +G2 +G3 +G4). We prove that if G1, G2, G3, and G4 are connected vertex-disjoint graphs and each has a spanning tree of vertex degree at most 4, then
b(G1 +G2 +G3 +G4) ≤ max{4,b(G1) + 1,b(G2) + 2,b(G3) + 2,b(G4) + 1}.
The basis number of the quadruple join of paths is also studied. In particular, we prove that
b(Pm +Pn +Pp +Pt ) = 4, m,t ≥ 5 and n, p ≥ 6.
Keywords
References
[1] S. Y. Alsardary and A. A. Ali, “The basis number of some special non-planar graphs,” Czechoslovak Math. J., vol. 53, no. 2, pp. 225–240, 2003.
[2] M. Y. Alzoubi and M. M. Jaradat, “The basis number of the cartesian product of a path with a circular ladder, a möbius ladder and a net,” Kyungpook Math. J., vol. 47, no. 2, pp. 165–174, 2007.
[3] M. Y. Alzoubi and M. M. Jaradat, “The basis number of the composition of theta graphs with some graph,” Ars Combinatoria, vol. 79, pp. 107–114, 2006.
[4] M. Y. Alzoubi and M. M. Jaradat, “On the basis num-ber of the composition of different ladders with some graphs,” Int. J. Math. Math. Sci., vol. 12, pp. 1861–1868, 2005.
[5] J. A. Banks and E. F. Schmeichel, “The basis number of the n-cube,” J. Combin. Theory Ser. B, vol. 33, no. 2, pp. 95–100, 1982.
[6] G. Chartrand and L. Lesniak, Graphs and Digraphs, 3rd ed. Chapman & Hall/CRC Press, 1996.
[7] F. Harary, Graph Theory, 3rd ed. Reading, MA: Addison-Wesley, 1972.
[8] M. M. Jaradat and M. Y. Alzoubi, “An upper bound of the basis number of the lexicographic product of graphs,” Australas. J. Combin., vol. 32, pp. 305–312, 2005.
[9] S. MacLane, “A combinatorial condition for planar graphs,” Fund. Math., vol. 28, pp. 22–32, 1937.
[10] E. F. Schmeichel, “The basis number of a graph,” J. Combin. Theory Ser. B, vol. 30, no. 2, pp. 123–129, 1981.
[11] A. A. Ali and G. T. Marougi, “The basis number of the lexicographic product of graphs,” Ars Combinatoria, vol. 36, pp. 271–282, 1993.
[12] A. A. Ali and G. T. Marougi, “The basis number of the cartesian product of some graphs,” J. Indian Math. Soc., vol. 58, no. 2, pp. 123–134, 1992.
[13] A. A. Ali, “The basis number of the join of graphs,” Arab J. Math., vol. 10, no. 1–2, pp. 21–32, 1989.
[14] G. T. Marougi, “On the basis number of ternary join of graphs,” Mu’tah Lil-Buhooth Wa Al-Dirasat, vol. 15, no. 1, pp. 35–42, 2000.
[15] M. M. Jaradat, M. Y. Alzoubi, and E. A. Rawashdeh, “The basis number of the lexicographic product of differ-ent ladders,” SUT J. Math., vol. 40, no. 2, pp. 91–101, 2004.
[16] G. T. Marougi, “On the basis number of semi-strong product of k2 with some special graphs,” Raf. J. Comput. Math., vol. 6, no. 3, pp. 173–181, 2009.
Cite This Article
Choose your preferred format
Publisher's Note
The statements, opinions, and data presented in this article are solely those of the author(s) and do not necessarily represent those of ASPG, the journal, or its editors. ASPG and the editors disclaim responsibility for any harm arising from the use of any ideas, methods, instructions, or products described in this article, to the fullest extent permitted by applicable law.