Search

An acyclic digraph in which every vertex has indegree at most i and outdegree at most j is called an (i , j) digraph for some positive integers i and j. The phylogeny graph of a digraph D has V (D) as the vertex set and an edge u v if and only if one of the following is true: (u , v) ∈ A (D) ; (v , u) ∈ A (D) ; (u , w) ∈ A (D) and (v , w) ∈ A (D) for some w ∈ V (D). A graph G is a phylogeny graph (resp. an (i , j) phylogeny graph) if there is an acyclic digraph D (resp. an (i , j) digraph D) such that the phylogeny graph of D is isomorphic to G. Lee et al. (2017) and Eoh and Kim (2021) studied the (2 , 2) phylogeny graphs, (1 , j) phylogeny graphs, (i , 1) phylogeny graphs, and (2 , j) phylogeny graphs. Their work was motivated by problems related to evidence propagation in a Bayesian network for which it is useful to know which acyclic digraphs have chordal moral graphs (phylogeny graphs are called moral graphs in Bayesian network theory). In this paper, we extend their work by giving necessary conditions of chordal (i , 2) phylogeny graphs. We go further to give necessary conditions of (i , j) phylogeny graphs by listing forbidden induced subgraphs. [ABSTRACT FROM AUTHOR]

Consider a connected simple graph G. Given a spanning tree T of G , for each edge e in G but not in T , a cycle C e is formed by adding the edge e to the path in T that connects the endpoints of e. The Minimum Spanning Tree Cycle Intersection problem (MSTCI for short) consists in finding a spanning tree for G that minimizes the number of intersections between this type of cycles. This problem was introduced in 2021 and its solution turned out to be difficult for general graphs, without an efficient algorithm to solve it. It was then conjectured that a solution of the problem for a graph that has a universal vertex u is the star centered at u. The conjecture was quickly proven true. In this note, we give a proof of the conjecture that is shorter than the one that has already been published. It is based on a single lemma about domination. We also explore the connections between this lemma and some graph classes, like chordal graphs and dually chordal graphs. [ABSTRACT FROM AUTHOR]

Chordal graphs are important in structural graph theory. Chordal digraphs are a digraph analogue of chordal graphs and have been a subject of active studies recently. Unlike chordal graphs, chordal digraphs lack many structural properties such as forbidden subdigraph or representation characterizations. In this paper we introduce the notion of semi-strict chordal digraphs which form a class strictly between chordal digraphs and chordal graphs. Semi-strict chordal digraphs have rich structural properties. We characterize semi-strict chordal digraphs in terms of knotting graphs, a notion analogous to the one introduced by Gallai for the study of comparability graphs. We also give forbidden subdigraph characterizations of semi-strict chordal digraphs within the classes of locally semicomplete digraphs and weakly quasi-transitive digraphs. [ABSTRACT FROM AUTHOR]

We define the k-cut complex of a graph G with vertex set V(G) to be the simplicial complex whose facets are the complements of sets of size k in V(G) inducing disconnected subgraphs of G. This generalizes the Alexander dual of a graph complex studied by Fröberg [Topics in Algebra, Part 2, PWN, Warsaw, 1990, pp. 57-70] and Eagon and Reiner [J. Pure Appl. Algebra, 130 (1998), pp. 265-275]. We describe the effect of various graph operations on the cut complex and study its shellability, homotopy type, and homology for various families of graphs, including trees, cycles, complete multipartite graphs, and the prism Kn X K2, using techniques from algebraic topology, discrete Morse theory, and equivariant poset topology. [ABSTRACT FROM AUTHOR]

A cocomparability graph is a graph whose complement admits a transitive orientation. An interval graph is the intersection graph of a family of intervals on the real line. In this paper we investigate the relationships between interval and cocomparability graphs. This study is motivated by recent results (Corneil et al., SIAM J. Comput. 42(3):792–807, 2013; Dusart et al., SIAM J. Comput. 50(3):1148–1153, 2021; Dusart and Habib, Discret. Appl. Math. 216:149–161, 2017) that show that for some problems, the algorithm used on interval graphs can also be used with small modifications on cocomparability graphs. Many of these algorithms are based on graph searches that preserve cocomparability orderings. First we propose a characterization of cocomparability graphs via a lattice structure on the set of their maximal cliques. Using this characterization we can prove that every maximal interval subgraph of a cocomparability graph G is also a maximal chordal subgraph of G. Although the size of this lattice of maximal cliques can be exponential in the size of the graph, it can be used as a framework to design and prove algorithms on cocomparability graphs. In particular we show that a new graph search, namely Local Maximal Neighborhood Search (LocalMNS) leads to an algorithm to find in linear time a maximal interval subgraph of a cocomparability graph which improves on the current state of knowledge. Although computing all simplicial vertices is known to be equivalent to the recognition of triangle-free graphs or boolean multiplication, see (Krastch and Spinrad, SIAM J. Comput. 36(2):310–325, 2007; Coudert and Ducoffe, SIAM J. Discrete Math. 32(1):682–694, 2018), we will show that our structural insights in cocomparability graphs together with the definition of a new graph search, allow us to achieve linear time on this class of graphs. [ABSTRACT FROM AUTHOR]

We prove various properties on the structure of groups whose power graph is chordal. Nilpotent groups with this property have been classified by (Electron J Combin 28(3):14, 2021). Here we classify the finite simple groups with chordal power graph, relative to typical number theoretic conditions. We do so by devising several sufficient conditions for the existence and non-existence of long cycles in power graphs of finite groups. We examine other natural group classes, including special linear, symmetric, generalized dihedral and quaternion groups, and we characterize direct products with chordal power graph. The classification problem is thereby reduced to directly indecomposable groups, and we further obtain a list of possible socles. Lastly, we give a general bound on the length of an induced path in chordal power graphs, providing another potential road to advance the classification beyond simple groups. [ABSTRACT FROM AUTHOR]

In 2018, Dvořák and Postle introduced a generalization of proper coloring, the so‐called DP‐coloring. For any graph G $G$, the DP‐chromatic number χDP(G) ${\chi }_{DP}(G)$ of G $G$ is defined analogously with the chromatic number χ(G) $\chi (G)$ of G $G$. In this article, we show that χDP(G∨Ks)=χ(G∨Ks) ${\chi }_{DP}(G\vee {K}_{s})=\chi (G\vee {K}_{s})$ holds for s=4(χ(G)+1)|E(G)|2χ(G)+1 $s=\unicode{x02308}\frac{4(\chi (G)+1)|E(G)|}{2\chi (G)+1}\unicode{x02309}$, where G∨Ks $G\vee {K}_{s}$ is the join of G $G$ and a complete graph with s $s$ vertices. As a result, ZDP(n)≤n2−(n+3)∕2 ${Z}_{DP}(n)\le {n}^{2}-(n+3)\unicode{x02215}2$ holds for every integer n≥2 $n\ge 2$, where ZDP(n) ${Z}_{DP}(n)$ is the minimum nonnegative integer s $s$ such that χDP(G∨Ks)=χ(G∨Ks) ${\chi }_{DP}(G\vee {K}_{s})=\chi (G\vee {K}_{s})$ holds for every graph G $G$ with n $n$ vertices. Our result improves the best current upper bound 1.5n2 $1.5{n}^{2}$ of ZDP(n) ${Z}_{DP}(n)$ due to Bernshteyn, Kostochka, and Zhu. [ABSTRACT FROM AUTHOR]

In 1966 Gallai asked whether all longest paths in a connected graph have nonempty intersection. This is not true in general and various counterexamples have been found. In this paper, we study the related question on longest cycles instead of longest paths (to make the question valid, we require 2‐connectivity). The answer for cycles is also negative and not so much attention has been given to it. Classes for which the answer is known to be positive are dually chordal graphs and 3‐trees. Perhaps the main open class for the question of both paths and cycles is the class of chordal graphs. In this paper, we show that all longest cycles intersect in graphs with treewidth at most three. This class of graphs includes several important subclasses of graphs, such as series‐parallel graphs and K5 ${K}_{5}$‐free chordal graphs. [ABSTRACT FROM AUTHOR]

An H-graph is one representable as the intersection graph of connected subgraphs of a suitable subdivision of a fixed graph H, introduced by Biró et al. (Discrete Mathematics 100:267–279, 1992). An H-graph is proper if the representing subgraphs of H can be chosen incomparable by the inclusion. In this paper, we focus on the isomorphism problem for S d -graphs and T-graphs, where S d is the star with d rays and T is an arbitrary fixed tree. Answering an open problem of Chaplick et al. (2016, personal communication), we provide an FPT-time algorithm for testing isomorphism and computing the automorphism group of S d -graphs when parameterized by d, which involves the classical group-computing machinery by Furst et al. (in Proceedings of 11th southeastern conference on combinatorics, graph theory, and computing, congressum numerantium 3, 1980). We also show that the isomorphism problem of S d -graphs is at least as hard as the isomorphism problem of posets of bounded width, for which no efficient combinatorial-only algorithm is known to date. Then we extend our approach to an XP-time algorithm for isomorphism of T-graphs when parameterized by the size of T. Lastly, we contribute an FPT-time combinatorial algorithm for isomorphism testing in the special case of proper S d - and T-graphs. [ABSTRACT FROM AUTHOR]

In this article, we first provide a modified definition of SuperHyperGraphs (SHG) and we call it Restricted SuperHyperGraphs (R-SHG). We then generalize the R-SHG to the neutrosophic graphs and then define the corresponding trees. In the following, we examine the Helly property for subtrees of SuperHyperGraphs.

This paper is inspired by the well known characterization of chordal graphs as the intersection graphs of subtrees of a tree. We consider families of induced trees of any graph and we prove that their recognition is NP-Complete. A consequence of this fact is that the concept of clique tree of chordal graphs cannot be widely generalized. Finally, we consider the fact that every graph is the intersection graph of induced trees of a bipartite graph and we characterize some classes that arise when we impose restrictions on the host bipartite graph. [ABSTRACT FROM AUTHOR]

Assume that G is a chordal graph with edge ideal I(G) and induced matching number ν(G). We denote the sth symbolic power of I(G) by I(G)(s). It is shown that reg(I(G)(s))=2s + ν(G) − 1 for every integer s ≥ 1. [ABSTRACT FROM AUTHOR]

The competitive diffusion game is a game-theoretic model of information spreading on a graph proposed by Alon et al. (2010). It models the diffusion process of information in social networks where several competitive companies want to spread their information, for example. The nature of this game strongly depends on the graph topology, and the relationship is studied from several aspects. In this paper, we investigate the existence of a pure Nash equilibrium of the two-player competitive diffusion game on chordal and its related graphs. We show that a pure Nash equilibrium always exists on split graphs, block graphs, and interval graphs, all of which are well-known subclasses of chordal graphs. On the other hand, we show that a pure Nash equilibrium does not always exist on (strongly) chordal graphs; the boundary of the existence of a pure Nash equilibrium is found. [ABSTRACT FROM AUTHOR]

Let t be a positive real number. A graph is called t-tough if the removal of any vertex set S that disconnects the graph leaves at most | S | / t components. The toughness of a graph is the largest t for which the graph is t -tough. A graph is minimally t -tough if the toughness of the graph is t and the deletion of any edge from the graph decreases the toughness. A graph is chordal if it does not contain an induced cycle of length at least 4. We characterize the minimally t -tough chordal graphs for all t ≤ 1 / 2. As a corollary, a characterization of minimally t -tough interval graphs is obtained for t ≤ 1 / 2. [ABSTRACT FROM AUTHOR]

For a poset P=(X,≤P), the strict-double-bound graph of P is the graph sDB(P) on V(sDB(P))=X for which vertices u and v of sDB(P) are adjacent if and only if u ≠ v and there exist elements x,y ∈ X distinct from u and v such that x ≤P u ≤P y and x ≤P v ≤P y. The strict-double-bound number ζ(G) of a graph G is defined as min{ n ; sDB(P) ≅ G ∪ Ǩn {for some poset P}. We obtain an upper bound of strict-double-bound numbers of graphs with a cut-set generating a complete subgraph. We also estimate upper bounds of strict-double-bound numbers of chordal graphs.

For a graph search algorithm, the end vertex problem is concerned with which vertices of a graph can be the last visited by this algorithm. We characterize all maximum cardinality searches on chordal graphs and derive from this characterization a polynomial-time algorithm for the end vertex problem of maximum cardinality searches on chordal graphs. It is complemented by a proof of NP-completeness of the same problem on weakly chordal graphs. We also show linear-time algorithms for deciding end vertices of breadth-first searches on interval graphs and end vertices of lexicographic depth-first searches on chordal graphs. [ABSTRACT FROM AUTHOR]

If for every two maximum independent sets A and B in a graph G there exists an automorphism of G that maps A to B , then we call G an α -iso-unique graph. We extend several known characterizations of trees that have a unique maximum independent set obtaining characterizations of α -iso-unique trees. Such trees either have the property that the deletion of any edge does not affect the independence number, or they have the central edge, which connects two isomorphic subtrees, and only the deletion of the central edge increases the independence number. One of the characterizations results in a linear time algorithm to recognize whether a given tree is α -iso-unique. In contrast, we prove that the problem of recognizing whether an arbitrary graph is α -iso-unique is not polynomial unless P = NP. Constructions of large families of α -iso-unique graphs are given involving simplicial vertices and chordal graphs. In particular, we show that every graph is an induced subgraph of an α -iso-unique graph. Finally, α -iso-unique graphs are characterized among Cartesian products G □ H of co-prime graphs G and H such that α (G □ H) = α (H) | V (G) |. [ABSTRACT FROM AUTHOR]

It is known that problems like Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal are polynomial time solvable in the class of chordal graphs. We consider these problems in a graph that has at most k vertices whose deletion results in a chordal graph when parameterized by k. While this investigation fits naturally into the recent trend of what is called 'structural parameterizations', here we assume that the deletion set is not given. One method to solve them is to compute a k-sized or an approximate (f(k) sized, for a function f) chordal vertex deletion set and then use the structural properties of the graph to design an algorithm. This method leads to at least k O (k) n O (1) running time when we use the known parameterized or approximation algorithms for finding a k-sized chordal deletion set on an n vertex graph. In this work, we design 2 O (k) n O (1) time algorithms for these problems. Our algorithms do not compute a chordal vertex deletion set (or even an approximate solution). Instead, we construct a tree decomposition of the given graph in 2 O (k) n O (1) time where each bag is a union of four cliques and O (k) vertices. We then apply standard dynamic programming algorithms over this special tree decomposition. This special tree decomposition can be of independent interest. Our algorithms are, what are sometimes called permissive in the sense that given an integer k, they detect whether the graph has no chordal vertex deletion set of size at most k or output the special tree decomposition and solve the problem. We also show lower bounds for the problems we deal with under the strong exponential time hypothesis. [ABSTRACT FROM AUTHOR]

For an integer k≥3, a k‐path vertex cover of a graph G=(V,E) is a set T⊆V that shares a vertex with every path subgraph of order k in G. The minimum cardinality of a k‐path vertex cover is denoted by ψk(G). We give estimates—mostly upper bounds—on ψk(G) in terms of various parameters, including vertex degrees and the number of vertices and edges. The problem is also considered on chordal graphs and planar graphs. [ABSTRACT FROM AUTHOR]

In this article, we first provide a modified definition of SuperHyperGraphs (SHG) and we call it Restricted SuperHyperGraphs (R-SHG). We then generalize the R-SHG to the neutrosophic graphs and then define the corresponding trees. In the following, we examine the Helly property for subtrees of SuperHyperGraphs. [ABSTRACT FROM AUTHOR]

The problem of verifying the nonnegativity of a function on a finite abelian group is a long-standing challenging problem. The basic representation theory of finite groups indicates that a function f on a finite abelian group G can be written as a linear combination of characters of irreducible representations of G by f (x) = ∑ χ ∈ G ˆ f ˆ (χ) χ (x) , where G ˆ is the dual group of G consisting of all characters of G and f ˆ (χ) is the Fourier coefficient of f at χ ∈ G ˆ. In this paper, we show that by performing the fast (inverse) Fourier transform, we are able to compute a sparse Fourier sum of squares (FSOS) certificate of f on a finite abelian group G with complexity that is quasi-linear in the order of G and polynomial in the FSOS sparsity of f. Moreover, for a nonnegative function f on a finite abelian group G and a subset S ⊆ G ˆ , we give a lower bound of the constant M such that f + M admits an FSOS supported on S. We demonstrate the efficiency of the proposed algorithm by numerical experiments on various abelian groups of orders up to 107. As applications, we also solve some combinatorial optimization problems and the sum of Hermitian squares (SOHS) problem by sparse FSOS. [ABSTRACT FROM AUTHOR]

Let G be a finite group. The reduced power graph of G is the undirected graph whose vertex set consists of all elements of G, and two distinct vertices x and y are adjacent if either ⟨x⟩⊂⟨y⟩ or ⟨y⟩⊂⟨x⟩. In this paper, we show that the reduced power graph of G is perfect and characterize all finite groups whose reduced power graphs are split graphs, cographs, chordal graphs, and threshold graphs. We also give complete classifications in the case of abelian groups, dihedral groups, and generalized quaternion groups.

• It is NP-complete to decide the local-equitable 2-colorability in chordal graphs. • Claw-free split graphs are local-equitably k -colorable when k ≤ 4. • A sufficient and sharp condition of local-equitable colorability is given. • The decision of local-equitable 2-coloring of planar graphs is solvable in polynomial time. An equitable k-partition (k ≥ 2) of a vertex set S is a partition of S into k disjoint subsets (may be empty sets) such that the sizes of any two subsets of S differ by at most one. A local-equitable k-coloring of G is an assignment of k colors to the vertices of G such that, for every maximal clique of G , the coloring of this clique forms an equitable k -partition of itself. The local-equitable coloring of G is a stronger version of clique-coloring of graphs. Chordal graphs are 2-clique-colorable but not necessarily local-equitably 2-colorable. In this paper, we prove that it is NP-complete to decide the local-equitable 2-colorability in chordal graphs and even in split graphs. In addition, we prove that claw-free split graphs are local-equitably k -colorable when k ≤ 4 , but not necessarily local-equitably k -colorable when k ≥ 5. A sufficient and sharp condition of local-equitably k -colorability is also given in claw-free split graphs. Secondly, we show that, given a split graph G , deciding the local-equitable k -colorability of G is solvable in polynomial time when k = ω (G) − 1 , where ω (G) is the clique number of G. At last, we prove that the decision problem of local-equitable 2-coloring of planar graphs is solvable in polynomial time. [ABSTRACT FROM AUTHOR]

A set S of vertices of a graph G is P 3 ⁎ -convex if there is no vertex outside S having two non-adjacent neighbors in S. The P 3 ⁎ -convex hull of S is the minimum P 3 ⁎ -convex set containing S. If the P 3 ⁎ -convex hull of S is V (G) , then S is a P 3 ⁎ -hull set. The minimum size of a P 3 ⁎ -hull set is the P 3 ⁎ -hull number of G. In this paper, we show that the problem of deciding whether the P 3 ⁎ -hull number of a chordal graph is at most k is NP -complete and present a linear-time algorithm to determine this parameter and provide a minimum P 3 ⁎ -hull set for unit interval graphs. [ABSTRACT FROM AUTHOR]

A graph G is a B 0 -VPG graph if one can associate a horizontal or vertical path on a rectangular grid with each vertex such that two vertices are adjacent if and only if the corresponding paths intersect in at least one grid-point. A graph G is a contact B 0 -VPG graph if it is a B 0 -VPG graph admitting a representation with no one-point paths, no two paths crossing, and no two paths sharing an edge of the grid. In this paper, we present a minimal forbidden induced subgraph characterisation of contact B 0 -VPG graphs within four special graph classes: chordal graphs, tree-cographs, P 4 -tidy graphs and P 5 -free graphs. Moreover, we present a polynomial-time algorithm for recognising chordal contact B 0 -VPG graphs. [ABSTRACT FROM AUTHOR]

A b-coloring of a graph is a proper coloring of its vertices such that each color class contains a vertex adjacent to at least one vertex of every other color class. The b-chromatic number of a graph is the largest integer k such that the graph has a b-coloring with k colors. In this work we present lower bounds for the b-chromatic number of a vertex-deleted subgraph of a graph, particularly regarding two important classes, claw-free graphs and chordal graphs. We also get bounds for the b-chromatic number of G − { x } , when G is a graph with large girth. [ABSTRACT FROM AUTHOR]

We study the neighborhood polynomial and the complexity of its computation for chordal graphs. The neighborhood polynomial of a graph is the generating function of subsets of its vertices that have a common neighbor. We introduce a parameter for chordal graphs called anchor width and an algorithm to compute the neighborhood polynomial which runs in polynomial time if the anchor width is polynomially bounded. The anchor width is the maximal number of different sub-cliques of a clique which appear as a common neighborhood. Furthermore we study the anchor width for chordal graphs and some subclasses such as chordal comparability graphs and chordal graphs with bounded leafage. The leafage of a chordal graphs is the minimum number of leaves in the host tree of a subtree representation. We show that the anchor width of a chordal graph is at most nl where l denotes the leafage. This shows that for some subclasses computing the neighborhood polynomial is possible in polynomial time while it is NP-hard for general chordal graphs. [ABSTRACT FROM AUTHOR]

Let lct(G) be the minimum cardinality of a set of vertices that intersects every longest cycle of a 2‐connected graph G. We show that lct(G)≤k−1 if G is a partial k‐tree and that lct(G)≤max{1,ω(G)−3} if G is chordal, where ω(G) is the cardinality of a maximum clique in G. Those results imply that all longest cycles intersect in 2‐connected series‐parallel graphs and in 3‐trees. [ABSTRACT FROM AUTHOR]

An acyclic digraph in which every vertex has indegree at most i and outdegree at most j is called an (i , j) digraph for some positive integers i and j. Lee et al. (2017) studied the phylogeny graphs of (2 , 2) digraphs and gave sufficient conditions and necessary conditions for a (2 , 2) digraph to have a chordal phylogeny graph. Their work was motivated by problems related to evidence propagation in a Bayesian network for which it is useful to know which acyclic digraphs have chordal moral graphs (phylogeny graphs are called moral graphs in Bayesian network theory). In this paper, we extend their work. We completely characterize the phylogeny graph of a (1 , i) digraph and an (i , 1) digraph, respectively, for any positive integer i. Then, we study phylogeny graphs of (2 , j) digraphs to show that the phylogeny graph of a (2 , j) digraph D is chordal if the underlying graph of D is chordal for any positive integer j. Especially, we show that as long as the underlying graph of a (2 , 2) digraph is chordal, its phylogeny graph is not only chordal but also planar. [ABSTRACT FROM AUTHOR]

Let be a graph and let be a positive integer. Let = and . The -token graph is the graph with vertex set and two vertices and are adjacent if and , where denotes the symmetric difference. In this paper we present several basic results on 2-token graphs.

This paper presents a novel approach to passivity enforcement of multiport frequency-dependent rational models. The strategy employs graph theory, and convex optimization to extend the positive-definite matrix completion problem to passive system completions. The main distinguishing feature of the proposed technique relative to those in the literature is that passivity compensations are only applied to those parameters contributing to passivity violations, in a completion manner. Numerical experiments using actual transformer data reveals that the proposed method results in models with increased accuracy. [ABSTRACT FROM AUTHOR]