Displaying similar documents to “An upper bound of the basis number of the strong product of graphs”

The basis number of some special non-planar graphs

Salar Y. Alsardary, Ali A. Ali (2003)

Czechoslovak Mathematical Journal

Similarity:

The basis number of a graph G was defined by Schmeichel to be the least integer h such that G has an h -fold basis for its cycle space. He proved that for m , n ≥ 5 , the basis number b ( K m , n ) of the complete bipartite graph K m , n is equal to 4 except for K 6 , 10 , K 5 , n and K 6 , n with n = 5 , 6 , 7 , 8 . We determine the basis number of some particular non-planar graphs such as K 5 , n and K 6 , n , n = 5 , 6 , 7 , 8 , and r -cages for r = 5 , 6 , 7 , 8 , and the Robertson graph.

The cycle-complete graph Ramsey number r(C₅,K₇)

Ingo Schiermeyer (2005)

Discussiones Mathematicae Graph Theory

Similarity:

The cycle-complete graph Ramsey number r(Cₘ,Kₙ) is the smallest integer N such that every graph G of order N contains a cycle Cₘ on m vertices or has independence number α(G) ≥ n. It has been conjectured by Erdős, Faudree, Rousseau and Schelp that r(Cₘ,Kₙ) = (m-1)(n-1)+1 for all m ≥ n ≥ 3 (except r(C₃,K₃) = 6). This conjecture holds for 3 ≤ n ≤ 6. In this paper we will present a proof for r(C₅,K₇) = 25.

The maximum genus, matchings and the cycle space of a graph

Hung-Lin Fu, Martin Škoviera, Ming-Chun Tsai (1998)

Czechoslovak Mathematical Journal

Similarity:

In this paper we determine the maximum genus of a graph by using the matching number of the intersection graph of a basis of its cycle space. Our result is a common generalization of a theorem of Glukhov and a theorem of Nebeský .