Displaying similar documents to “The basis number of some special non-planar graphs”

An upper bound on the basis number of the powers of the complete graphs

Salar Y. Alsardary (2001)

Czechoslovak Mathematical Journal

Similarity:

The basis number of a graph G is defined by Schmeichel to be the least integer h such that G has an h -fold basis for its cycle space. MacLane showed that a graph is planar if and only if its basis number is ≤ 2 . Schmeichel proved that the basis number of the complete graph K n is at most 3 . We generalize the result of Schmeichel by showing that the basis number of the d -th power of K n is at most 2 d + 1 .

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.

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

Join of two graphs admits a nowhere-zero 3 -flow

Saieed Akbari, Maryam Aliakbarpour, Naryam Ghanbari, Emisa Nategh, Hossein Shahmohamad (2014)

Czechoslovak Mathematical Journal

Similarity:

Let G be a graph, and λ the smallest integer for which G has a nowhere-zero λ -flow, i.e., an integer λ for which G admits a nowhere-zero λ -flow, but it does not admit a ( λ - 1 ) -flow. We denote the minimum flow number of G by Λ ( G ) . In this paper we show that if G and H are two arbitrary graphs and G has no isolated vertex, then Λ ( G ∨ H ) ≤ 3 except two cases: (i) One of the graphs G and H is K 2 and the other is 1 -regular. (ii) H = K 1 and G is a graph with at least one isolated vertex or a component whose every...