A Degree Condition Implying Ore-Type Condition for Even [2,b]-Factors in Graphs

Shoichi Tsuchiya; Takamasa Yashima

Displaying similar documents to “A Degree Condition Implying Ore-Type Condition for Even [2,b]-Factors in Graphs”

$F$ -continuous graphs

Gary Chartrand, Elzbieta B. Jarrett, Farrokh Saba, Ebrahim Salehi, Ping Zhang (2001)

Czechoslovak Mathematical Journal

Similarity:

For a nontrivial connected graph $F$ , the $F$ -degree of a vertex $v$ in a graph $G$ is the number of copies of $F$ in $G$ containing $v$ . A graph $G$ is $F$ -continuous (or $F$ -degree continuous) if the $F$ -degrees of every two adjacent vertices of $G$ differ by at most 1. All $P_{3}$ -continuous graphs are determined. It is observed that if $G$ is a nontrivial connected graph that is $F$ -continuous for all nontrivial connected graphs $F$ , then either $G$ is regular or $G$ is a path. In the case of a 2-connected graph $F$ , however,...

Note on independent sets of a graph

Jaroslav Ivančo (1994)

Mathematica Bohemica

Similarity:

Let the number of $k$ -element sets of independent vertices and edges of a graph $G$ be denoted by $n (G, k)$ and $m (G, k)$ , respectively. It is shown that the graphs whose every component is a circuit are the only graphs for which the equality $n (G, k) = m (G, k)$ is satisfied for all values of $k$ .

Degree-continuous graphs

John Gimbel, Ping Zhang (2001)

Czechoslovak Mathematical Journal

Similarity:

A graph $G$ is degree-continuous if the degrees of every two adjacent vertices of $G$ differ by at most 1. A finite nonempty set $S$ of integers is convex if $k \in S$ for every integer $k$ with $min (S) \leq k \leq max (S)$ . It is shown that for all integers $r > 0$ and $s \geq 0$ and a convex set $S$ with $min (S) = r$ and $max (S) = r + s$ , there exists a connected degree-continuous graph $G$ with the degree set $S$ and diameter $2 s + 2$ . The minimum order of a degree-continuous graph with a prescribed degree set is studied. Furthermore, it is shown that for every graph $G$ and convex...

The Degree-Diameter Problem for Outerplanar Graphs

Peter Dankelmann, Elizabeth Jonck, Tomáš Vetrík (2017)

Discussiones Mathematicae Graph Theory

Similarity:

For positive integers Δ and D we define nΔ,D to be the largest number of vertices in an outerplanar graph of given maximum degree Δ and diameter D. We prove that [...] nΔ,D=ΔD2+O (ΔD2−1) $n_{Δ, D} = Δ^{\frac{D}{2}} + O (Δ^{\frac{D}{2} - 1})$ is even, and [...] nΔ,D=3ΔD−12+O (ΔD−12−1) $n_{Δ, D} = 3 Δ^{\frac{D - 1}{2}} + O (Δ^{\frac{D - 1}{2} - 1})$ if D is odd. We then extend our result to maximal outerplanar graphs by showing that the maximum number of vertices in a maximal outerplanar graph of maximum degree Δ and diameter D asymptotically equals nΔ,D.

Results on $F$ -continuous graphs

Anna Draganova (2009)

Czechoslovak Mathematical Journal

Similarity:

For any nontrivial connected graph $F$ and any graph $G$ , the of a vertex $v$ in $G$ is the number of copies of $F$ in $G$ containing $v$ . $G$ is called if and only if the $F$ -degrees of any two adjacent vertices in $G$ differ by at most 1; $G$ is if the $F$ -degrees of all vertices in $G$ are the same. This paper classifies all $P_{4}$ -continuous graphs with girth greater than 3. We show that for any nontrivial connected graph $F$ other than the star $K_{1, k}$ , $k \geq 1$ , there exists a regular graph that is not $F$ -continuous. If...

Lower bounds on signed edge total domination numbers in graphs

H. Karami, S. M. Sheikholeslami, Abdollah Khodkar (2008)

Czechoslovak Mathematical Journal

Similarity:

The open neighborhood $N_{G} (e)$ of an edge $e$ in a graph $G$ is the set consisting of all edges having a common end-vertex with $e$ . Let $f$ be a function on $E (G)$ , the edge set of $G$ , into the set ${- 1, 1}$ . If $\sum_{x \in N_{G} (e)} f (x) \geq 1$ for each $e \in E (G)$ , then $f$ is called a signed edge total dominating function of $G$ . The minimum of the values $\sum_{e \in E (G)} f (e)$ , taken over all signed edge total dominating function $f$ of $G$ , is called the signed edge total domination number of $G$ and is denoted by $γ_{s t}^{'} (G)$ . Obviously, $γ_{s t}^{'} (G)$ is defined only for graphs $G$ which have no connected...

Solution to the problem of Kubesa

Mariusz Meszka (2008)

Discussiones Mathematicae Graph Theory

Similarity:

An infinite family of T-factorizations of complete graphs $K_{2 n}$ , where 2n = 56k and k is a positive integer, in which the set of vertices of T can be split into two subsets of the same cardinality such that degree sums of vertices in both subsets are not equal, is presented. The existence of such T-factorizations provides a negative answer to the problem posed by Kubesa.

Graphs with large double domination numbers

Michael A. Henning (2005)

Discussiones Mathematicae Graph Theory

Similarity:

In a graph G, a vertex dominates itself and its neighbors. A subset S ⊆ V(G) is a double dominating set of G if S dominates every vertex of G at least twice. The minimum cardinality of a double dominating set of G is the double domination number $γ_{\times 2} (G)$ . If G ≠ C₅ is a connected graph of order n with minimum degree at least 2, then we show that $γ_{\times 2} (G) \leq 3 n / 4$ and we characterize those graphs achieving equality.