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

Salar Y. Alsardary

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 \geq 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 \in 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)} \geq \frac{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)}) \cap A (γ) | \geq 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 \geq 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 \geq 4$ we reduce the problem of characterizing graphs $G$ such that $P_{k} (G) ≅ G$ to graphs without cycles of length exceeding $k$ .

Cycle-pancyclism in bipartite tournaments II

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 contained in T[V(γ)]? It is proved that for an even k in the range (n+6)/2 ≤ k ≤ n-2, there exists a directed cycle $C_{h (k)}$ of length h(k), h(k) ∈ k,k-2 with $| A (C_{h (k)}) \cap A (γ) | \geq h (k) - 4$ and the result is best possible. In a previous paper a similar result for 4 ≤ k ≤ (n+4)/2 was...

Pairs of forbidden class of subgraphs concerning $K_{1, 3}$ and P₆ to have a cycle containing specified vertices

Takeshi Sugiyama, Masao Tsugaki (2009)

Discussiones Mathematicae Graph Theory

Similarity:

In [3], Faudree and Gould showed that if a 2-connected graph contains no $K_{1, 3}$ and P₆ as an induced subgraph, then the graph is hamiltonian. In this paper, we consider the extension of this result to cycles passing through specified vertices. We define the families of graphs which are extension of the forbidden pair $K_{1, 3}$ and P₆, and prove that the forbidden families implies the existence of cycles passing through specified vertices.