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 2 Next

Displaying 21 – 40 of 200

Showing per page

Bounding neighbor-connectivity of Abelian Cayley graphs

Lynne L. Doty (2011)

Discussiones Mathematicae Graph Theory

For the notion of neighbor-connectivity in graphs whenever a vertex is subverted the entire closed neighborhood of the vertex is deleted from the graph. The minimum number of vertices whose subversion results in an empty, complete, or disconnected subgraph is called the neighbor-connectivity of the graph. Gunther, Hartnell, and Nowakowski have shown that for any graph, neighbor-connectivity is bounded above by κ. Doty has sharpened that bound in abelian Cayley graphs to approximately (1/2)κ. The...

Bounds for the rainbow connection number of graphs

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 show some new bounds for the rainbow connection number of graphs depending on the minimum degree and other graph parameters. Moreover, we discuss sharpness of some of these bounds.

Bounds on the subdominant eigenvalue involving group inverses with applications to graphs

Stephen J. Kirkland, Neumann, Michael, Bryan L. Shader (1998)

Czechoslovak Mathematical Journal

Let A be an n × n symmetric, irreducible, and nonnegative matrix whose eigenvalues are λ 1 > λ 2 ≥ ... ≥ λ n . In this paper we derive several lower and upper bounds, in particular on λ 2 and λ n , but also, indirectly, on μ = max 2 ≤ i ≤ n | λ i | . The bounds are in terms of the diagonal entries of the group generalized inverse, Q # , of the singular and irreducible M-matrix Q = λ 1 I - A . Our starting point is a spectral resolution for Q # . We consider the case of equality in some of these inequalities and we apply our results to the algebraic connectivity of undirected...

Competition hypergraphs of digraphs with certain properties I. Strong connectedness

Martin Sonntag, Hanns-Martin Teichert (2008)

Discussiones Mathematicae Graph Theory

If D = (V,A) is a digraph, its competition hypergraph 𝓒𝓗(D) has the vertex set V and e ⊆ V is an edge of 𝓒𝓗(D) iff |e| ≥ 2 and there is a vertex v ∈ V, such that e = {w ∈ V|(w,v) ∈ A}. We tackle the problem to minimize the number of strong components in D without changing the competition hypergraph 𝓒𝓗(D). The results are closely related to the corresponding investigations for competition graphs in Fraughnaugh et al. [3].

Connected domatic number in planar graphs

Bert L. Hartnell, Douglas F. Rall (2001)

Czechoslovak Mathematical Journal

A dominating set in a graph G is a connected dominating set of G if it induces a connected subgraph of G . The connected domatic number of G is the maximum number of pairwise disjoint, connected dominating sets in V ( G ) . We establish a sharp lower bound on the number of edges in a connected graph with a given order and given connected domatic number. We also show that a planar graph has connected domatic number at most 4 and give a characterization of planar graphs having connected domatic number 3.

Connected odd dominating sets in graphs

Yair Caro, William F. Klostermeyer, Raphael Yuster (2005)

Discussiones Mathematicae Graph Theory

An odd dominating set of a simple, undirected graph G = (V,E) is a set of vertices D ⊆ V such that |N[v] ∩ D| ≡ 1 mod 2 for all vertices v ∈ V. It is known that every graph has an odd dominating set. In this paper we consider the concept of connected odd dominating sets. We prove that the problem of deciding if a graph has a connected odd dominating set is NP-complete. We also determine the existence or non-existence of such sets in several classes of graphs. Among other results, we prove there...

Currently displaying 21 – 40 of 200