Geodesic
An upper bound of the basis number of the strong product of graphs
Discussiones Mathematicae. Graph Theory, Tome 25 (2005) no. 3, pp. 391-406

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

The basis number of a graph G is defined to be the least integer d such that there is a basis B of the cycle space of G such that each edge of G is contained in at most d members of B. In this paper we give an upper bound of the basis number of the strong product of a graph with a bipartite graph and we show that this upper bound is the best possible.
Keywords: basis number, cycle space, strong product 
Jaradat, Mohammed. An upper bound of the basis number of the strong product of graphs. Discussiones Mathematicae. Graph Theory, Tome 25 (2005) no. 3, pp. 391-406. http://geodesic.mathdoc.fr/item/DMGT_2005_25_3_a15/
@article{DMGT_2005_25_3_a15,
     author = {Jaradat, Mohammed},
     title = {An upper bound of the basis number of the strong product of graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {391--406},
     year = {2005},
     volume = {25},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2005_25_3_a15/}
}
TY  - JOUR
AU  - Jaradat, Mohammed
TI  - An upper bound of the basis number of the strong product of graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2005
SP  - 391
EP  - 406
VL  - 25
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DMGT_2005_25_3_a15/
LA  - en
ID  - DMGT_2005_25_3_a15
ER  - 
%0 Journal Article
%A Jaradat, Mohammed
%T An upper bound of the basis number of the strong product of graphs
%J Discussiones Mathematicae. Graph Theory
%D 2005
%P 391-406
%V 25
%N 3
%U http://geodesic.mathdoc.fr/item/DMGT_2005_25_3_a15/
%G en
%F DMGT_2005_25_3_a15

[1] A.A. Ali, The basis number of complete multipartite graphs, Ars Combin. 28 (1989) 41-49.

[2] A.A. Ali and G.T. Marougi, The basis number of the strong product of graphs, Mu'tah Lil-Buhooth Wa Al-Dirasat 7 (1) (1992) 211-222.

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

[4] A.S. Alsardary, An upper bound on the basis number of the powers of the complete graphs, Czechoslovak Math. J. 51 (126) (2001) 231-238, doi: 10.1023/A:1013734628017.

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

[6] R. Diestel, Graph Theory, Graduate Texts in Mathematics, 173 (Springer-Verlag, New York, 1997).

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

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

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

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

[11] P.K. Jha, Hamiltonian decompositions of product of cycles, Indian J. Pure Appl. Math. 23 (1992) 723-729.

[12] P.K. Jha and G. Slutzki, A note on outerplanarity of product graphs, Zastos. Mat. 21 (1993) 537-544.

[13] S. MacLane, A combinatorial condition for planar graphs, Fundamenta Math. 28 (1937) 22-32.

[14] G. Sabidussi, Graph multiplication, Math. Z. 72 (1960) 446-457, doi: 10.1007/BF01162967.

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

[16] P.M. Weichsel, The Kronecker product of graphs, Proc. Amer. Math. Soc. 13 (1962) 47-52, doi: 10.1090/S0002-9939-1962-0133816-6.