Download PDF - On the basis number and the minimum cycle bases of the wreath product of some graphs iAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

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

Authors 1

Affiliations

  1. Department of Mathematics, Yarmouk University, Irbid-Jordan

Abstract

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.

Keywords

ENG
cycle space, basis number, cycle basis, wreath product

Bibliography

  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.
Discussiones Mathematicae Graph Theory
2006/26/1
Export to PBN, Opens in new tab
Pages:
113-134
Main language of publication
English
Received
2005-03-03
Accepted
2005-09-09
Published
2006

DOI: 10.7151/dmgt.1306

Exact and natural sciences