On the basis number and the minimum cycle bases of the wreath product of some graphs i

Mohammed M.M. Jaradat

Discussiones Mathematicae Graph Theory, Tome 26 (2006), p. 113-134 / Harvested from The Polish Digital Mathematics Library

Résumé

A construction of a minimum cycle bases for the wreath product of some classes of graphs is presented. Moreover, the basis numbers for the wreath product of the same classes are determined.

Détail

Publié le : 2006-01-01

Zbl 1104.05036

EUDML-ID : urn:eudml:doc:270783

Bibliographie

[000] [1] M. Anderson and M. Lipman, The wreath product of graphs, in: Graphs and Applications (Boulder, Colo., 1982), (Wiley-Intersci. Publ., Wiley, New York, 1985) 23-39.

[001] [2] A.A. Ali, The basis number of complete multipartite graphs, Ars Combin. 28 (1989) 41-49. | Zbl 0728.05058

[002] [3] A.A. Ali, The basis number of the direct product of paths and cycles, Ars Combin. 27 (1989) 155-163.

[003] [4] A.A. Ali and G.T. Marougi, The basis number of cartesian product of some graphs, J. Indian Math. Soc. 58 (1992) 123-134. | Zbl 0880.05055

[004] [5] A.S. Alsardary and J. Wojciechowski, The basis number of the powers of the complete graph, Discrete Math. 188 (1998) 13-25, doi: 10.1016/S0012-365X(97)00271-9. | Zbl 0958.05074

[005] [6] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (America Elsevier Publishing Co. Inc., New York, 1976). | Zbl 1226.05083

[006] [7] W.-K. Chen, On vector spaces associated with a graph, SIAM J. Appl. Math. 20 (1971) 525-529, doi: 10.1137/0120054.

[007] [8] D.M. Chickering, D. Geiger and D. HecKerman, On finding a cycle basis with a shortest maximal cycle, Inform. Process. Lett. 54 (1994) 55-58, doi: 10.1016/0020-0190(94)00231-M. | Zbl 0875.68685

[008] [9] L.O. Chua and L. Chen, On optimally sparse cycles and coboundary basis for a linear graph, IEEE Trans. Circuit Theory 20 (1973) 54-76.

[009] [10] G.M. Downs, V.J. Gillet, J.D. Holliday and M.F. Lynch, Review of ring perception algorithms for chemical graphs, J. Chem. Inf. Comput. Sci. 29 (1989) 172-187, doi: 10.1021/ci00063a007.

[010] [11] W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition (Wiley, New York, 2000).

[011] [12] W. Imrich and P. Stadler, Minimum cycle bases of product graphs, Australas. J. Combin. 26 (2002) 233-244. | Zbl 1009.05078

[012] [13] M.M.M. Jaradat, On the basis number of the direct product of graphs, Australas. J. Combin. 27 (2003) 293-306. | Zbl 1021.05060

[013] [14] M.M.M. Jaradat, The basis number of the direct product of a theta graph and a path, Ars Combin. 75 (2005) 105-111. | Zbl 1074.05051

[014] [15] M.M.M. Jaradat, An upper bound of the basis number of the strong product of graphs, Discuss. Math. Graph Theory 25 (2005) 391-406, doi: 10.7151/dmgt.1291. | Zbl 1107.05049

[015] [16] M.M.M. Jaradat, M.Y. Alzoubi and E.A. Rawashdeh, The basis number of the Lexicographic product of different ladders, SUT J. Math. 40 (2004) 91-101. | Zbl 1072.05049

[016] [17] A. Kaveh, Structural Mechanics, Graph and Matrix Methods. Research Studies Press (Exeter, UK, 1992). | Zbl 0858.73002

[017] [18] G. Liu, On connectivities of tree graphs, J. Graph Theory 12 (1988) 435-459, doi: 10.1002/jgt.3190120318. | Zbl 0649.05044

[018] [19] S. MacLane, A combinatorial condition for planar graphs, Fundamenta Math. 28 (1937) 22-32. | Zbl 0015.37501

[019] [20] M. Plotkin, Mathematical basis of ring-finding algorithms in CIDS, J. Chem. Doc. 11 (1971) 60-63, doi: 10.1021/c160040a013.

[020] [21] E.F. Schmeichel, The basis number of a graph, J. Combin. Theory (B) 30 (1981) 123-129, doi: 10.1016/0095-8956(81)90057-5. | Zbl 0385.05031

[021] [22] P. Vismara, Union of all the minimum cycle bases of a graph, Electr. J. Combin. 4 (1997) 73-87. | Zbl 0885.05101

[022] [23] D.J.A. Welsh, Kruskal's theorem for matroids, Proc. Cambridge Phil, Soc. 64 (1968) 3-4, doi: 10.1017/S030500410004247X. | Zbl 0157.55302