All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 13 Next

Displaying 241 – 260 of 299

Showing per page

Graphs with large double domination numbers

Michael A. Henning (2005)

Discussiones Mathematicae Graph Theory

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 γ × 2 ( G ) . If G ≠ C₅ is a connected graph of order n with minimum degree at least 2, then we show that γ × 2 ( G ) ≤ 3 n / 4 and we characterize those graphs achieving equality.

Graphs with Large Generalized (Edge-)Connectivity

Xueliang Li, Yaping Mao (2016)

Discussiones Mathematicae Graph Theory

The generalized k-connectivity κk(G) of a graph G, introduced by Hager in 1985, is a nice generalization of the classical connectivity. Recently, as a natural counterpart, we proposed the concept of generalized k-edge-connectivity λk(G). In this paper, graphs of order n such that [...] for even k are characterized.

Graphs with rainbow connection number two

Arnfried Kemnitz, Ingo Schiermeyer (2011)

Discussiones Mathematicae Graph Theory

An edge-coloured graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colours. The rainbow connection number of a connected graph G, denoted rc(G), is the smallest number of colours that are needed in order to make G rainbow connected. In this paper we prove that rc(G) = 2 for every connected graph G of order n and size m, where n - 1 2 + 1 ≤ m ≤ n 2 - 1 . We also characterize graphs with rainbow connection number two and large clique number.

Graphs with small additive stretch number

Dieter Rautenbach (2004)

Discussiones Mathematicae Graph Theory

The additive stretch number s a d d ( G ) of a graph G is the maximum difference of the lengths of a longest induced path and a shortest induced path between two vertices of G that lie in the same component of G.We prove some properties of minimal forbidden configurations for the induced-hereditary classes of graphs G with s a d d ( G ) ≤ k for some k ∈ N₀ = 0,1,2,.... Furthermore, we derive characterizations of these classes for k = 1 and k = 2.

Graphs with small diameter determined by their D -spectra

Ruifang Liu, Jie Xue (2018)

Czechoslovak Mathematical Journal

Let G be a connected graph with vertex set V ( G ) = { v 1 , v 2 , ... , v n } . The distance matrix D ( G ) = ( d i j ) n × n is the matrix indexed by the vertices of G , where d i j denotes the distance between the vertices v i and v j . Suppose that λ 1 ( D ) ≥ λ 2 ( D ) ≥ ⋯ ≥ λ n ( D ) are the distance spectrum of G . The graph G is said to be determined by its D -spectrum if with respect to the distance matrix D ( G ) , any graph having the same spectrum as G is isomorphic to G . We give the distance characteristic polynomial of some graphs with small diameter, and also prove that these graphs are determined...

Currently displaying 241 – 260 of 299