Displaying similar documents to “An upper bound on the basis number of the powers of the complete 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.

On ( 4 , 1 ) * -choosability of toroidal graphs without chordal 7-cycles and adjacent 4-cycles

Haihui Zhang (2013)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

A graph G is called ( k , d ) * -choosable if for every list assignment L satisfying | L ( v ) | = k for all v ∈ V ( G ) , there is an L -coloring of G such that each vertex of G has at most d neighbors colored with the same color as itself. In this paper, it is proved that every toroidal graph without chordal 7-cycles and adjacent 4-cycles is ( 4 , 1 ) * -choosable.

The structure and existence of 2-factors in iterated line graphs

Michael Ferrara, Ronald J. Gould, Stephen G. Hartke (2007)

Discussiones Mathematicae Graph Theory

Similarity:

We prove several results about the structure of 2-factors in iterated line graphs. Specifically, we give degree conditions on G that ensure L²(G) contains a 2-factor with every possible number of cycles, and we give a sufficient condition for the existence of a 2-factor in L²(G) with all cycle lengths specified. We also give a characterization of the graphs G where L k ( G ) contains a 2-factor.

A Fan-Type Heavy Pair Of Subgraphs For Pancyclicity Of 2-Connected Graphs

Wojciech Wideł (2016)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a graph on n vertices and let H be a given graph. We say that G is pancyclic, if it contains cycles of all lengths from 3 up to n, and that it is H-f1-heavy, if for every induced subgraph K of G isomorphic to H and every two vertices u, v ∈ V (K), dK(u, v) = 2 implies [...] min⁡dG(u),dG(v)≥n+12 min { d G ( u ) , d G ( v ) } ≥ n + 1 2 . In this paper we prove that every 2-connected K1,3, P5-f1-heavy graph is pancyclic. This result completes the answer to the problem of finding f1-heavy pairs of subgraphs implying...

Cycle-pancyclism in bipartite tournaments I

Hortensia Galeana-Sánchez (2004)

Discussiones Mathematicae Graph Theory

Similarity:

Let T be a hamiltonian bipartite tournament with n vertices, γ a hamiltonian directed cycle of T, and k an even number. In this paper, the following question is studied: What is the maximum intersection with γ of a directed cycle of length k? It is proved that for an even k in the range 4 ≤ k ≤ [(n+4)/2], there exists a directed cycle C h ( k ) of length h(k), h(k) ∈ k,k-2 with | A ( C h ( k ) ) ∩ A ( γ ) | ≥ h ( k ) - 3 and the result is best possible. In a forthcoming paper the case of directed cycles of length k, k even and k <...

Graphs isomorphic to their path graphs

Martin Knor, Ľudovít Niepel (2002)

Mathematica Bohemica

Similarity:

We prove that for every number n ≥ 1 , the n -iterated P 3 -path graph of G is isomorphic to G if and only if G is a collection of cycles, each of length at least 4. Hence, G is isomorphic to P 3 ( G ) if and only if G is a collection of cycles, each of length at least 4. Moreover, for k ≥ 4 we reduce the problem of characterizing graphs G such that P k ( G ) ≅ G to graphs without cycles of length exceeding k .