Displaying similar documents to “ F -continuous graphs”

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 ∈ S for every integer k with min ( S ) ≤ k ≤ max ( S ) . It is shown that for all integers r > 0 and s ≥ 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...

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 ≥ 1 , there exists a regular graph that is not F -continuous. If...

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 .

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

Shoichi Tsuchiya, Takamasa Yashima (2017)

Discussiones Mathematicae Graph Theory

Similarity:

For a graph G and even integers b ⩾ a ⩾ 2, a spanning subgraph F of G such that a ⩽ degF (x) ⩽ b and degF (x) is even for all x ∈ V (F) is called an even [a, b]-factor of G. In this paper, we show that a 2-edge-connected graph G of order n has an even [2, b]-factor if [...] max degG (x),degG (y)⩾max 2n2+b,3 max { deg G ( x ) , deg G ( y ) } ≥ max 2 n 2 + b , 3 for any nonadjacent vertices x and y of G. Moreover, we show that for b ⩾ 3a and a > 2, there exists an infinite family of 2-edge-connected graphs G of order n with δ(G) ⩾ a...

Vertex-disjoint stars in graphs

Katsuhiro Ota (2001)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper, we give a sufficient condition for a graph to contain vertex-disjoint stars of a given size. It is proved that if the minimum degree of the graph is at least k+t-1 and the order is at least (t+1)k + O(t²), then the graph contains k vertex-disjoint copies of a star K 1 , t . The condition on the minimum degree is sharp, and there is an example showing that the term O(t²) for the number of uncovered vertices is necessary in a sense.

A bound on the k -domination number of a graph

Lutz Volkmann (2010)

Czechoslovak Mathematical Journal

Similarity:

Let G be a graph with vertex set V ( G ) , and let k ≥ 1 be an integer. A subset D ⊆ V ( G ) is called a if every vertex v ∈ V ( G ) - D has at least k neighbors in D . The k -domination number γ k ( G ) of G is the minimum cardinality of a k -dominating set in G . If G is a graph with minimum degree δ ( G ) ≥ k + 1 , then we prove that γ k + 1 ( G ) ≤ | V ( G ) | + γ k ( G ) 2 . In addition, we present a characterization of a special class of graphs attaining equality in this inequality.