Geodesic
Minimal cycle bases of the lexicographic product of graphs
Discussiones Mathematicae. Graph Theory, Tome 28 (2008) no. 2, pp. 229-247

Voir la notice de l'article provenant de la source Library of Science

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: cycle space, lexicographic product, cycle basis 
Jaradat, M. Minimal cycle bases of the lexicographic product of graphs. Discussiones Mathematicae. Graph Theory, Tome 28 (2008) no. 2, pp. 229-247. http://geodesic.mathdoc.fr/item/DMGT_2008_28_2_a2/
@article{DMGT_2008_28_2_a2,
     author = {Jaradat, M.},
     title = {Minimal cycle bases of the lexicographic product of graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {229--247},
     year = {2008},
     volume = {28},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2008_28_2_a2/}
}
TY  - JOUR
AU  - Jaradat, M.
TI  - Minimal cycle bases of the lexicographic product of graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2008
SP  - 229
EP  - 247
VL  - 28
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2008_28_2_a2/
LA  - en
ID  - DMGT_2008_28_2_a2
ER  - 
%0 Journal Article
%A Jaradat, M.
%T Minimal cycle bases of the lexicographic product of graphs
%J Discussiones Mathematicae. Graph Theory
%D 2008
%P 229-247
%V 28
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2008_28_2_a2/
%G en
%F DMGT_2008_28_2_a2

[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.