Download PDF - Minimal cycle bases of the lexicographic product of graphsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Minimal cycle bases of the lexicographic product of graphs

Authors 1

Affiliations

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

Abstract

A construction of minimum cycle bases of the lexicographic product of graphs is presented. Moreover, the length of a longest cycle of a minimal cycle basis is determined.

Keywords

ENG
cycle space, lexicographic product, cycle basis

Bibliography

  1. M. Anderson and M. Lipman, The wreath product of graphs, Graphs and Applications (Boulder, Colo., 1982), (Wiley-Intersci. Publ., Wiley, New York, 1985) 23-39.
  2. F. Berger, Minimum Cycle Bases in Graphs (PhD thesis, Munich, 2004).
  3. Z. Bradshaw and M.M.M. Jaradat, Minimum cycle bases for direct products of K₂ with complete graphs, Australasian J. Combin. (accepted).
  4. W.-K. Chen, On vector spaces associated with a graph, SIAM J. Appl. Math. 20 (1971) 525-529, doi: 10.1137/0120054.
  5. D.M. Chickering, D. Geiger and D. HecKerman, On finding a cycle basis with a shortest maximal cycle, Information Processing Letters 54 (1994) 55-58, doi: 10.1016/0020-0190(94)00231-M.
  6. 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.
  7. 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.
  8. R. Hammack, Minimum cycle bases of direct products of bipartite graphs, Australasian J. Combin. 36 (2006) 213-221.
  9. R. Hammack, Minimum cycle bases of direct products of complete graphs, Information Processing Letters 102 (2007) 214-218, doi: 10.1016/j.ipl.2006.12.012.
  10. W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition (Wiley, New York, 2000).
  11. W. Imrich and P. Stadler, Minimum cycle bases of product graphs, Australasian J. Combin. 26 (2002) 233-244.
  12. M.M.M. Jaradat, On the basis number and the minimum cycle bases of the wreath product of some graphs I, Discuss. Math. Graph Theory 26 (2006) 113-134, doi: 10.7151/dmgt.1306.
  13. M.M.M. Jaradat, M.Y. Alzoubi and E.A. Rawashdeh, The basis number of the Lexicographic product of different ladders, SUT Journal of Mathematics 40 (2004) 91-101.
  14. A. Kaveh, Structural Mechanics, Graph and Matrix Methods. Research Studies Press (Exeter, UK, 1992).
  15. A. Kaveh and R. Mirzaie, Minimal cycle basis of graph products for the force method of frame analysis, Communications in Numerical Methods in Engineering, to appear, doi: 10.1002/cnm.979.
  16. G. Liu, On connectivities of tree graphs, J. Graph Theory 12 (1988) 435-459, doi: 10.1002/jgt.3190120318.
  17. M. Plotkin, Mathematical basis of ring-finding algorithms in CIDS, J. Chem. Doc. 11 (1971) 60-63, doi: 10.1021/c160040a013.
  18. P. Vismara, Union of all the minimum cycle bases of a graph, Electr. J. Combin. 4 (1997) 73-87.
  19. 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
2008/28/2
Export to PBN, Opens in new tab
Pages:
229-247
Main language of publication
English
Received
2007-05-23
Accepted
2008-04-17
Published
2008

DOI: 10.7151/dmgt.1403

Exact and natural sciences