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

Mohammed M.M. Jaradat

Discussiones Mathematicae Graph Theory (2005)

  • Volume: 25, Issue: 3, page 391-406
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Mohammed M.M. Jaradat. "An upper bound of the basis number of the strong product of graphs." Discussiones Mathematicae Graph Theory 25.3 (2005): 391-406. <http://eudml.org/doc/270222>.

@article{MohammedM2005,
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.},
author = {Mohammed M.M. Jaradat},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {basis number; cycle space; strong product; tree},
language = {eng},
number = {3},
pages = {391-406},
title = {An upper bound of the basis number of the strong product of graphs},
url = {http://eudml.org/doc/270222},
volume = {25},
year = {2005},
}

TY - JOUR
AU - Mohammed M.M. Jaradat
TI - An upper bound of the basis number of the strong product of graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2005
VL - 25
IS - 3
SP - 391
EP - 406
AB - 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.
LA - eng
KW - basis number; cycle space; strong product; tree
UR - http://eudml.org/doc/270222
ER -

References

top
  1. [1] A.A. Ali, The basis number of complete multipartite graphs, Ars Combin. 28 (1989) 41-49. Zbl0728.05058
  2. [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. Zbl0880.05055
  3. [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. Zbl0880.05055
  4. [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. [5] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (America Elsevier Publishing Co. Inc., New York, 1976). Zbl1226.05083
  6. [6] R. Diestel, Graph Theory, Graduate Texts in Mathematics, 173 (Springer-Verlag, New York, 1997). 
  7. [7] W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition (Wiley, New York, 2000). 
  8. [8] W. Imrich and P. Stadler, Minimum cycle bases of product graphs, Australas. J. Combin. 26 (2002) 233-244. Zbl1009.05078
  9. [9] M.M.M. Jaradat, On the basis number of the direct product of graphs, Australas. J. Combin. 27 (2003) 293-306. Zbl1021.05060
  10. [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. Zbl1074.05051
  11. [11] P.K. Jha, Hamiltonian decompositions of product of cycles, Indian J. Pure Appl. Math. 23 (1992) 723-729. Zbl0783.05080
  12. [12] P.K. Jha and G. Slutzki, A note on outerplanarity of product graphs, Zastos. Mat. 21 (1993) 537-544. Zbl0770.05042
  13. [13] S. MacLane, A combinatorial condition for planar graphs, Fundamenta Math. 28 (1937) 22-32. Zbl0015.37501
  14. [14] G. Sabidussi, Graph multiplication, Math. Z. 72 (1960) 446-457, doi: 10.1007/BF01162967. Zbl0093.37603
  15. [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. Zbl0385.05031
  16. [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. Zbl0102.38801

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.