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

• Autorzy: Mohammed M.M. Jaradat
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

cycle space; basis number; cycle basis; wreath product

Kategorie tematyczne

• 05C75: Structural characterization of families of graphs
• 05C38: Paths and cycles

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2006
• Tom: 26
• Numer: 1
• Strony: 113-134

Daty

wydano

2006

otrzymano

2005-03-03

poprawiono

2005-09-09

Twórcy

autor

Mohammed M.M. Jaradat

• Department of Mathematics, Yarmouk University, Irbid-Jordan

Bibliografia

• [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.
• [2] A.A. Ali, The basis number of complete multipartite graphs, Ars Combin. 28 (1989) 41-49.
• [3] A.A. Ali, The basis number of the direct product of paths and cycles, Ars Combin. 27 (1989) 155-163.
• [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.
• [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.
• [6] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (America Elsevier Publishing Co. Inc., New York, 1976).
• [7] W.-K. Chen, On vector spaces associated with a graph, SIAM J. Appl. Math. 20 (1971) 525-529, doi: 10.1137/0120054.
• [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.
• [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.
• [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.
• [11] W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition (Wiley, New York, 2000).
• [12] W. Imrich and P. Stadler, Minimum cycle bases of product graphs, Australas. J. Combin. 26 (2002) 233-244.
• [13] M.M.M. Jaradat, On the basis number of the direct product of graphs, Australas. J. Combin. 27 (2003) 293-306.
• [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.
• [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.
• [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.
• [17] A. Kaveh, Structural Mechanics, Graph and Matrix Methods. Research Studies Press (Exeter, UK, 1992).
• [18] G. Liu, On connectivities of tree graphs, J. Graph Theory 12 (1988) 435-459, doi: 10.1002/jgt.3190120318.
• [19] S. MacLane, A combinatorial condition for planar graphs, Fundamenta Math. 28 (1937) 22-32.
• [20] M. Plotkin, Mathematical basis of ring-finding algorithms in CIDS, J. Chem. Doc. 11 (1971) 60-63, doi: 10.1021/c160040a013.
• [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.
• [22] P. Vismara, Union of all the minimum cycle bases of a graph, Electr. J. Combin. 4 (1997) 73-87.
• [23] D.J.A. Welsh, Kruskal's theorem for matroids, Proc. Cambridge Phil, Soc. 64 (1968) 3-4, doi: 10.1017/S030500410004247X.

Identyfikatory

DOI

10.7151/dmgt.1306