Volume 4 • Issue 1 • PP: 01-05 • 2024
The basis number of connected vertex-disjoint graphs
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 try to find an upper bound for b (G_1+G_2+G_3+G_4). We prove that, if G_1,G_2,G_3 and G_4 are connected vertex-disjoint graphs and each has a spanning tree of vertex degree not more than 4, then b(G_1+G_2+G_3+G_4)≤max{4,b(G_1)+1,b(G_2)+2,b(G_3) +2,b (G_4)+1}. The basis number of quadruple join of paths will be studied, where we prove that b p_m+ p_n+p_p+p_t) =4, ∀m,t≥5 and n,p≥6.
Keywords
References
[1] Ali, A.A.; Marougi,G.T., (1993), The basis number of the lexicographic product of graphs, Ars combinatoria, Vol.36, pp.271-282.
[2] Ali, A.A.; Marougi,G.T., (1992), The basis number of the Cartesian product of some graphs, J. Indian Math. Soc., Vol. 58, No.2, pp. 123-134.
[3] Ali , A.A.,(1989), The basis number of the join of graphs ,Arab J. Maths., Vol. 10 No. 1&2, pp. 21-32.
[4] Alsardary, S.Y.; Ali, A.A., (2003), The basis number of some special non planar graphs, Czechoslovak Math. J., Vol. 53, No.2, pp. 225-240.
[5] Alzoubi, M.Y.; Jaradat, M.M., (2007), 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.
[6] Alzoubi, M.Y.; Jaradat, M.M., (2006), The basis number of the composition of theta graphs with some graph, Ars combinatoria, Vol.79, pp.107-114.
[7] Alzoubi, M.Y.; Jaradat, M.M., (2005), On the basis number of the composition of different ladders with some graphs, International Journal of Mathematics and Mathematical Sciences, Vol. 12, pp. 1861-1868.
[8] Banks, J.A.; Schmeichel, E.F., (1982), The basis number of the n-cube, J. combin. Theory, Ser. B, Vol. 33, No.2, pp. 95-100.
[9] Chartrand, G.; Lesniak, L., (1996), Graphs and Digraphs, 3d ed., Chapman & Hall, CRC. Press.
[10] Harary, F., (1972), Graph Theory, 3rd ed., Reading, Massachusetts, Addison-Wesly.
[11] Jaradat, M.M.; Alzoubi, M.Y., (2005), An upper bound of the basis number of the lexicographic product of graphs, Australas J. comb., Vol. 32, pp. 305-312.
[12] Jaradat, M.M.; Alzoubi, M.Y.; Rawashdeh, E.A., (2004), The basis number of the lexicographic product of different ladders, SUT Journal of Mathematics, Vol. 40, No.2, pp. 91-101.
[13] Maclane, S., (1937), A combinatorial condition for planar graphs, Fund. Math., Vol. 28, pp. 22-32.
[14] Marougi, G.T., (2009), On the basis number of semi-strong product of K2 with some special graphs, Raf.J. of comp. & Maths., Vol. 6, No.3, pp. 173-181.
[15] Marougi, G.T.,(2000),On the basis number of ternary join of graphs, Mu' tah Lil-Buhooth Wa Al-Dirasat Vol.15, No.1, pp.35-42.
[16] Schmeichel, E.F., (1981), The basis number of a graph, J. combin. Theory, Ser. B, Vol. 3٠, No.2, pp. 123-129.
Cite This Article
Choose your preferred format