All regular multigraphs of even order and high degree are 1-factorable.
Alternating connectivity of digraphs
Alternating connectivity of tournaments
An upper bound for the minimum degree of a graph
Applications of relaxed submodularity.
Asymptotics for the probability of connectedness and the distribution of number of components.
Atoms of cyclic connectivity in cubic graphs
Block-closed subgraphs and q-partitions of graphs
Bounding neighbor-connectivity of Abelian Cayley graphs
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
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
Let be an symmetric, irreducible, and nonnegative matrix whose eigenvalues are . In this paper we derive several lower and upper bounds, in particular on and , but also, indirectly, on . The bounds are in terms of the diagonal entries of the group generalized inverse, , of the singular and irreducible M-matrix . Our starting point is a spectral resolution for . We consider the case of equality in some of these inequalities and we apply our results to the algebraic connectivity of undirected...
Characterizations of m-connected graphs
Characterizing families of cuts that can be represented by axis-parallel rectangles.
Competition hypergraphs of digraphs with certain properties I. Strong connectedness
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 Components of Arithmetic Graphs.
Connected domatic number in planar graphs
A dominating set in a graph is a connected dominating set of if it induces a connected subgraph of . The connected domatic number of is the maximum number of pairwise disjoint, connected dominating sets in . 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 graphs containing a given connected graph as a unique greatest common subgraph.
Connected odd dominating sets in graphs
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...
Connectivity, Line-Connectivity and J-Connection of the Total Graph.
Connectivity of path graphs.