A vertex set D in a finite undirected graph G is an efficient dominating set (e.d.s for short) of G if every vertex of G is dominated by exactly one vertex of D. The Efficient Domination (ED) ...problem, which asks for the existence of an e.d.s. in G, is known to be NP-complete even for very restricted graph classes such as for 2P3-free chordal graphs while it is solvable in polynomial time for P6-free chordal graphs (and even for P6-free graphs). A standard reduction from the NP-complete Exact Cover problem shows that ED is NP-complete for a very special subclass of chordal graphs generalizing split graphs. The reduction implies that ED is NP-complete e.g. for double-gem-free chordal graphs while it is solvable in linear time for gem-free chordal graphs (by various reasons such as bounded clique-width, distance-hereditary graphs, chordal square etc.), and ED is NP-complete for butterfly-free chordal graphs while it is solvable in linear time for 2P2-free graphs.
We show that (weighted) ED can be solved in polynomial time for H-free chordal graphs when H is net, extended gem, or S1,2,3.
Let G be a connected graph with vertex set V(G). The distance, dG(u,v), between vertices u and v in G is defined as the length of a shortest path between u and v in G. The distance matrix of G is the ...matrix D(G)=(dG(u,v))u,v∈V(G). The second largest distance eigenvalue of G is the second largest one in the spectrum of D(G). We show that any connected graph with the second largest distance eigenvalue less than −12 is chordal, and characterize those bicyclic graphs and split graphs with the second largest distance eigenvalue less than −12.
The Terrain Guarding problem, a variant of the famous Art Gallery problem, has garnered significant attention over the last two decades in Computational Geometry from the viewpoint of complexity and ...approximability. Both the continuous and discrete versions of the problem were shown to be NP-Hard in King and Krohn (2010) and to admit a PTAS (Krohn et al., 2014; Friedrichs et al., 2016). The biggest unsolved question regarding this problem is if it is fixed-parameter tractable with respect to the size of the guard set. In this paper, we present two theorems that establish a relationship between a restricted case of the ONE-SIDED TERRAIN GUARDING problem and the Clique Cover problem in chordal graphs. These theorems were proved in Katz and Roisman (2008) for a special class of terrains called orthogonal terrains and were used to present a FPT algorithm with respect to the parameter that we require for DISCRETE ORTHOGONAL TERRAIN GUARDING in Ashok et al. (2018). We hope that the results obtained in this paper can, in future work, be used to produce such an algorithm for Discrete Terrain Guarding.
In this work we assess subclasses of chordal graphs focusing on special structures such as maximal cliques and minimal vertex separators. A subclass is presented and characterized, the non-inclusion ...chordal graphs, graphs in which there is no proper containment between any two minimal vertex separators. A hierarchical structure of classes is outlined, showing that some well-known subclasses of chordal graphs are subclasses of the newly defined class. In order to characterize non-inclusion chordal graphs, a supporting structure, the clique-bipartite graph of a chordal graph is defined.
3 have recently determined the maximum number of edges of a chordal graph with a maximum degree less than $d$ and the matching number at most $\nu$ by exhibiting a family of chordal graphs achieving ...this bound. We provide simple proof of their result.
Let G=(V,E) be a graph where V and E are the vertex and edge sets, respectively. For two disjoint subsets A and B of V, we say AdominatesB if every vertex of B is adjacent to at least one vertex of ...A. A vertex partition π={V1,V2,…,Vk} of G is called a transitive partition of size k if Vi dominates Vj for all 1≤i<j≤k. In this article, we study a variation of transitive partition, namely 2-transitive partition. For two disjoint subsets A and B of V, we say A 2-dominatesB if every vertex of B is adjacent to at least two vertices of A. A vertex partition π={V1,V2,…,Vk} of G is called a 2-transitive partition of size k if Vi2-dominates Vj for all 1≤i<j≤k. The Maximum 2-Transitivity Problem is to find a 2-transitive partition of a given graph with the maximum number of parts. We show that the decision version of this problem is NP-complete for chordal and bipartite graphs. On the positive side, we design three linear-time algorithms for solving Maximum 2-Transitivity Problem in trees, split, and bipartite chain graphs.
We show that if a graph G satisfies certain conditions, then the connectivity of neighbourhood complex N(G) is strictly less than the vertex connectivity of G. As an application, we give a relation ...between the connectivity of the neighbourhood complex and the vertex connectivity for stiff chordal graphs, and for weakly triangulated graphs satisfying certain properties. Next, we consider graphs with a vertex v such that for any k-subset S of neighbours of v, there exists a vertex vS≠v such that S is subset of neighbours of vS. We prove that for any graph G with a vertex v as above, N(G−{v}) is (k−1)-connected implies that N(G) is (k−1)-connected. We use this to show that:(i) neighbourhood complexes of queen and king graphs are simply connected and (ii) if G is a non-complete stiff chordal graph, then vertex connectivity of G is n+1 if and only if Conn(N(G))=n.
We consider the size of the smallest set of vertices required to intersect every longest path in a chordal graph. Such sets are known as longest path transversals. We show that if ω(G) is the clique ...number of a chordal graph G, then there is a transversal of order at most 4⌈ω(G)5⌉. We also consider the analogous question for longest cycles, and show that if G is a 2-connected chordal graph then there is a transversal intersecting all longest cycles of order at most 2⌈ω(G)3⌉.
A widespread methodology for modeling modern day information, which consists of high-dimensional digital measurements, is to use vine copulas; they can flexibly encode the underlying dependence ...structure of the data. Here we introduce a new algorithm to encode complete and truncated vines in a matrix, and as such, storing the information content of vines in a virtual environment. The conditional independence structure encoded by a vine can be represented in graph terms. We summarize these representations, and show equivalence between them. We show a new result, namely that when a perfect elimination ordering of a vine structure is given, then it can be uniquely represented with a matrix. Nápoles has shown a way to represent vines in a matrix, and we algorithmify this previous approach, while also showing a new method for constructing such a matrix, through cherry tree sequences, which can also store truncated vines. Moreover, this new algorithm can directly build truncated vines by storing each level separately - without building up the entire vine, which would be necessary in Nápoles' algorithm. We calculate the runtime of these algorithms. Lastly, we prove that these two matrix-building algorithms are equivalent if the same perfect elimination ordering is being used.
PDF
