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.
Connectivity of path graphs
We prove a necessary and sufficient condition under which a connected graph has a connected P₃-path graph. Moreover, an analogous condition for connectivity of the Pₖ-path graph of a connected graph which does not contain a cycle of length smaller than k+1 is derived.
Connectivity of planar graphs.
Connectivity, toughness, spanning trees of bounded degree, and the spectrum of regular graphs
The eigenvalues of graphs are related to many of its combinatorial properties. In his fundamental work, Fiedler showed the close connections between the Laplacian eigenvalues and eigenvectors of a graph and its vertex-connectivity and edge-connectivity. We present some new results describing the connections between the spectrum of a regular graph and other combinatorial parameters such as its generalized connectivity, toughness, and the existence of spanning trees with bounded degree.
Constructing hypohamiltonian snarks with cyclic connectivity 5 and 6.
Constructions for type I trees with nonisomorphic Perron branches
A tree is classified as being type I provided that there are two or more Perron branches at its characteristic vertex. The question arises as to how one might construct such a tree in which the Perron branches at the characteristic vertex are not isomorphic. Motivated by an example of Grone and Merris, we produce a large class of such trees, and show how to construct others from them. We also investigate some of the properties of a subclass of these trees. Throughout, we exploit connections between...
Containers and wide diameters of
The intersection graph of a graph has for vertices all the induced paths of order 3 in . Two vertices in are adjacent if the corresponding paths in are not disjoint. A -container between two different vertices and in a graph is a set of internally vertex disjoint paths between and . The length of a container is the length of the longest path in it. The -wide diameter of is the minimum number such that there is a -container of length at most between any pair of different...
Contractible edges in some -connected graphs
An edge of a -connected graph is said to be -contractible (or simply contractible) if the graph obtained from by contracting (i.e., deleting and identifying its ends, finally, replacing each of the resulting pairs of double edges by a single edge) is still -connected. In 2002, Kawarabayashi proved that for any odd integer , if is a -connected graph and contains no subgraph , then has a -contractible edge. In this paper, by generalizing this result, we prove that for any integer...
Cut-vertices and domination in graphs
The paper studies the domatic numbers and the total domatic numbers of graphs having cut-vertices.
Cutwidth of the de Bruijn graph
Cycles with a given number of vertices from each partite set in regular multipartite tournaments
If is a vertex of a digraph , then we denote by and the outdegree and the indegree of , respectively. A digraph is called regular, if there is a number such that for all vertices of . A -partite tournament is an orientation of a complete -partite graph. There are many results about directed cycles of a given length or of directed cycles with vertices from a given number of partite sets. The idea is now to combine the two properties. In this article, we examine in particular, whether...
Cyclic connectivity classes of directed graphs.