Download PDF - An upper bound of the basis number of the strong product of graphsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

An upper bound of the basis number of the strong product of graphs

Authors 1

Affiliations

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

Abstract

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

ENG
basis number, cycle space, strong product

Bibliography

  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.
Discussiones Mathematicae Graph Theory
2005/25/3
Export to PBN, Opens in new tab
Pages:
391-406
Main language of publication
English
Received
2004-06-29
Accepted
2005-01-03
Published
2005

DOI: 10.7151/dmgt.1291

Exact and natural sciences