Search

In this paper, we present the class of δ EFL graphs and then prove a generalized statement of the Erdős–Faber–Lovász conjecture for this graph class. Then, the Erdős–Faber–Lovász conjecture follows for every graph in this class. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Fuzhou University is the property of Journal of Fuzhou University, Editorial Department and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

A directed projection graph of the n -dimensional hypercube on the two-dimensional plane is successfully created. Any n -variable Boolean function can be easily transformed to an induced subgraph of the projection. Therefore, the discussions on n -variable Boolean functions only need to focus on a two-dimensional planar graph. Some mathematical theories on the projection graph and the induced subgraph are established, and some properties and characteristics of a balanced linearly separable Boolean function (BLSBF) are uncovered. In particular, the sub-hypercube decompositions of BLSBF is easily represented on the projection, and meanwhile, the enumeration scheme for counting the number of n -variable BLSBFs is developed by using equivalence classification and conformal transformation. With the aid of the directed projection grap constructed in this paper, one can further study many difficult problems in some fields such as Boolean functions and artificial neural networks. [ABSTRACT FROM AUTHOR]

In 1992, Bagga, Beineke, and Varma introduced the concept of the super line graph of index of a graph denoted by The vertices of are the -subsets of and two vertices and are adjacent if there exist and such that and are adjacent edges in They also defined the line completion number of graph G to be the minimum index for which is complete. They found the line completion number for certain classes of graphs. In this paper, we find the line completion number of hypercube for every .

This work elaborates on the old problem of measuring the degree of similarity, say f (G , H) , between a pair of connected graphs G and H, not necessarily of the same order. The choice of a similarity index f depends essentially on the graph properties that are considered as important in a given context. As relevant information on a graph, one may consider for instance its degree sequence, its characteristic polynomial, and so on. We explore some new similarity indices based on nonstandard spectral information contained in the graphs under comparison. By nonstandard spectral information in a graph, we mean the set of complementarity eigenvalues of the adjacency matrix. From such a spectral perspective, two distinct graphs G and H are viewed as highly similar if they share a large number of complementarity eigenvalues. This basic idea will be cast in a rigorous mathematical formalism. [ABSTRACT FROM AUTHOR]

We resolve the computational complexity of Graph Isomorphism for classes of graphs characterized by two forbidden induced subgraphs H 1 and H 2 for all but six pairs (H 1 , H 2) . Schweitzer had previously shown that the number of open cases was finite, but without specifying the open cases. Grohe and Schweitzer proved that Graph Isomorphism is polynomial-time solvable on graph classes of bounded clique-width. Our work combines known results such as these with new results. By exploiting a relationship between Graph Isomorphism and clique-width, we simultaneously reduce the number of open cases for boundedness of clique-width for (H 1 , H 2) -free graphs to five. [ABSTRACT FROM AUTHOR]

An odd hole in a graph is an induced cycle with odd length greater than 3. In an earlier paper (with Sophie Spirkl), solving a longstanding open problem, we gave a polynomial-time algorithm to test if a graph has an odd hole. We subsequently showed that, for every t, there is a polynomial-time algorithm to test whether a graph contains an odd hole of length at least t. In this article, we give an algorithm that finds a shortest odd hole, if one exists. [ABSTRACT FROM AUTHOR]

A graph is H‐free if it has no induced subgraph isomorphic to H, and |G| denotes the number of vertices of G. A conjecture of Conlon, Sudakov and the second author asserts that: For every graph H, there exists ε>0 such that in every H‐free graph G with |G| there are two disjoint sets of vertices, of sizes at least ε|G|ε and ε|G|, complete or anticomplete to each other. This is equivalent to: The "sparse linear conjecture": For every graph H, there exists ε>0 such that in every H‐free graph G with |G|>1, either some vertex has degree at least ε|G|, or there are two disjoint sets of vertices, of sizes at least ε|G|ε and ε|G|, anticomplete to each other. We prove a number of partial results toward the sparse linear conjecture. In particular, we prove it holds for a large class of graphs H, and we prove that something like it holds for all graphs H. More exactly, say H is "almost‐bipartite" if H is triangle‐free and V(H) can be partitioned into a stable set and a set inducing a graph of maximum degree at most one. (This includes all graphs that arise from another graph by subdividing every edge at least once.) Our main result is: The sparse linear conjecture holds for all almost‐bipartite graphs H. (It remains open when H is the triangle K3.) There is also a stronger theorem: For every almost‐bipartite graph H, there exist ε,t>0 such that for every graph G with |G|>1 and maximum degree less than ε|G|, and for every c with 00 such that in every H‐free graph G with |G|>1 vertices, either some vertex has degree at least ε|G|, or there are two disjoint sets A,B of vertices with |A|⋅|B|≥ε|G|1+ε, anticomplete to each other. [ABSTRACT FROM AUTHOR]

Generalized minimum spanning tree problem, which has several real-world applications like telecommunication network designing, is related to combinatorial optimization problems. This problem belongs to the NP-hard class and is a minimum tree on a clustered graph spanning one node from each cluster. Although exact and metaheuristic algorithms have been applied to solve the problems successfully, obtaining an optimal solution using these approaches and other optimization tools has been a challenge. In this paper, an attempt is made to achieve a sub-optimal solution using a network of learning automata (LA). This algorithm assigns an LA to every cluster so that the number of actions is the same as that of nodes in the corresponding cluster. At each iteration, LAs select one node from their clusters. Then, the weight of the constructed generalized spanning tree is considered as a criterion for rewarding or penalizing the selected actions. The experimental results on a set of 20 benchmarks of TSPLIB demonstrate that the proposed approach is significantly faster than the other mentioned algorithms. The results indicate that the new algorithm is competitive in terms of solution quality. [ABSTRACT FROM AUTHOR]

Truemper configurations are four types of graphs (namely thetas, wheels, prisms and pyramids) that play an important role in the proof of several decomposition theorems for hereditary graph classes. In this paper, we prove two structure theorems: one for graphs with no thetas, wheels and prisms as induced subgraphs, and one for graphs with no thetas, wheels and pyramids as induced subgraphs. A consequence is a polynomial time recognition algorithms for these two classes. In Part II of this series we generalize these results to graphs with no thetas and wheels as induced subgraphs, and in Parts III and IV, using the obtained structure, we solve several optimization problems for these graphs. [ABSTRACT FROM AUTHOR]

We say a graph G has a Hamiltonian path if it has a path containing all vertices of G. For a graph G , let σ 2 (G) denote the minimum degree sum of two nonadjacent vertices of G ; restrictions on σ 2 (G) are known as Ore-type conditions. Given an integer t ≥ 5 , we prove that if a connected graph G on n vertices satisfies σ 2 (G) > t − 3 t − 2 n , then G has either a Hamiltonian path or an induced subgraph isomorphic to K 1 , t. Moreover, we characterize all n -vertex graphs G where σ 2 (G) = t − 3 t − 2 n and G has neither a Hamiltonian path nor an induced subgraph isomorphic to K 1 , t. This is an analogue of a recent result by Momège (2018), who investigated the case when t = 4. [ABSTRACT FROM AUTHOR]

The set of all unlabeled induced subgraphs of a finite graph G can be made into a poset by defining H 1 ≤ H 2 iff H 1 is a subgraph of H 2 . This paper discusses some of the connections between the graph properties of G and the order theoretic properties of this poset. This paper then restricts this class of subgraphs to only connected unlabeled induced subgraphs and looks at some of the order theoretic properties of that poset. [ABSTRACT FROM AUTHOR]

Let G be a connected graph with n vertices, maximum vertex degree Δ ≥ 2 and nullity η. In Q. Zhou et al. (2018) [22] , it was conjectured that η ≤ (Δ − 2) n + 2 Δ − 1 and the upper bound is attained if and only if G is a cycle C n with n divisible by 4 or a complete bipartite graph K n / 2 , n / 2. In the present paper, this conjecture is proved. [ABSTRACT FROM AUTHOR]

A graph is H-free if it has no induced subgraph isomorphic to H. We characterize all graphs H for which there are only finitely many minimal non-3-colorable H-free graphs. Such a characterization was previously known only in the case when H is connected. This solves a problem posed by Golovach et al. As a second result, we characterize all graphs H for which there are only finitely many H-free minimal obstructions for list 3-colorability. [ABSTRACT FROM AUTHOR]

In this paper, we study an important problem in secret sharing that determines the exact value or bound for the complexity. First, we use the induced subgraph complexity of the graph G with access structure Γ to obtain a lower bound on the complexity of the graph G. Then, applying decomposition techniques, we obtain an upper bound on the complexity of the graph G. We determine the exact values of the complexity for each of the ten graph access structures on seven participants. Also, we improve the value bound of the complexity for the six graph access structures with seven participants.

We show that triangle‐free graphs that do not contain an induced subgraph isomorphic to a subdivision of K4 are 3‐colorable. This proves a conjecture of Trotignon and Vušković [J. Graph Theory. 84 (2017), no. 3, pp. 233–248]. [ABSTRACT FROM AUTHOR]

Abstract We prove that every triangle-free planar graph of order n and size m has an induced linear forest with at least 9 n − 2 m 11 vertices, and thus at least 5 n + 8 11 vertices. Furthermore, we show that there are triangle-free planar graphs on n vertices whose largest induced linear forest has order ⌈ n 2 ⌉ + 1. [ABSTRACT FROM AUTHOR]

Abstract A homogeneous set of a graph G is a set X of vertices such that 2 ≤ | X | < | V (G) | and no vertex in V (G) − X has both a neighbor and a non-neighbor in X. A graph is prime if it has no homogeneous set. We present an algorithm to decide whether a class of graphs given by a finite set of forbidden induced subgraphs contains infinitely many non-isomorphic prime graphs. [ABSTRACT FROM AUTHOR]

In this article, we propose a polynomial‐time algorithm to test whether a given graph contains a subdivision of K4 as an induced subgraph. This continues the study of detecting an induced subdivision of H for some fixed graph H, which is still far from being complete. Our result answers a question by Chudnovsky et al. and Lévêque et al. [ABSTRACT FROM AUTHOR]

In this article, we propose a polynomial‐time algorithm to test whether a given graph contains a subdivision of K4 as an induced subgraph. This continues the study of detecting an induced subdivision of H for some fixed graph H, which is still far from being complete. Our result answers a question by Chudnovsky et al. and Lévêque et al. [ABSTRACT FROM AUTHOR]

Necessary conditions for an undirected graph G to contain a graph H as induced subgraph involving the smallest ordinary or the largest normalized Laplacian eigenvalue of G are presented.

The Wiener index W ( G ) of a connected graph G is defined as the sum of distances between all pairs of vertices in G . In 1991, Šoltés posed the problem of finding all graphs G such that the equality W ( G ) = W ( G − v ) holds for all their vertices v . Up to now, the only known graph with this property is the cycle C 11 . Our main object of study is a relaxed version of this problem: Find graphs for which Wiener index does not change when a particular vertex v is removed. In an earlier paper we have shown that there are infinitely many graphs with the vertex v of degree 2 satisfying this property. In this paper we focus on removing a higher degree vertex and we show that for any k  ≥ 3 there are infinitely many graphs with a vertex v of degree k satisfying W ( G ) = W ( G − v ) . In addition, we solve an analogous problem if the degree of v is n − 1 or n − 2 . Furthermore, we prove that dense graphs cannot be a solutions of Šoltes’s problem. We conclude that the relaxed version of Šoltés’s problem is rich with a solutions and we hope that this can provide an insight into the original problem of Šoltés. [ABSTRACT FROM AUTHOR]

Featured Application: MUIS (Minimal Unique Induced Subgraph) query can be used in many potential applications, such as subgraph retrieval, graph visualization, representative subgraph discovery and vertex property exploration. In this paper, a novel type of interesting subgraph query is proposed: Minimal Unique Induced Subgraph (MUIS) query. Given a (large) graph G and a query vertex (position) q in the graph, can we find an induced subgraph containing q with the minimal number of vertices that is unique in G? MUIS query has many potential applications, such as subgraph retrieval, graph visualization, representative subgraph discovery and vertex property exploration. The formal definition of MUIS is given and the properties are discussed in this paper. The baseline and EQA (Efficient Query Answering) algorithms are proposed to solve the MUIS query problem under the filtering-validation framework. In the EQA algorithm, the Breadth First Search (BFS)-based candidate set generation strategy is proposed to ensure the minimality property of MUIS; the matched vertices-based pruning strategy is proposed to prune useless candidate sets and the unnecessary subgraph isomorphism; and the query position-based subgraph isomorphism is proposed to check efficiently the uniqueness of the subgraphs. Experiments are carried on real datasets and synthetic datasets to verify the effectiveness and efficiency of the proposed algorithm under novel measurements. The influencing factors of the process speed are discussed at last in the paper. [ABSTRACT FROM AUTHOR]

Abstract: We prove the titular statement. This settles a problem of Chvátal from 1973 and encompasses earlier results of Thomassen, who showed it for K3, and Collier and Schmeichel, who proved it for bipartite graphs. We also show that for every outerplanar graph there exists a planar hypohamiltonian graph containing it as an induced subgraph. [ABSTRACT FROM AUTHOR]

The graphs with no five-vertex induced path are still not understood. But in the triangle-free case, we can do this and one better; we give an explicit construction for all triangle-free graphs with no six-vertex induced path. Here are three examples: the 16-vertex Clebsch graph, the graph obtained from an 8-cycle by making opposite vertices adjacent, and the graph obtained from a complete bipartite graph by subdividing a perfect matching. We show that every connected triangle-free graph with no six-vertex induced path is an induced subgraph of one of these three (modulo some twinning and duplication). [ABSTRACT FROM AUTHOR]

A long-standing conjecture asserts that there exists a constant c>0 such that every graph of order n without isolated vertices contains an induced subgraph of order at least cn with all degrees odd. Scott (Comb Probab Comput 1:335-349, 1992) proved that every graph G has an induced subgraph of order at least |V(G)|/(2χ(G)) with all degrees odd, where χ(G) is the chromatic number of G, this implies the conjecture for graphs with bounded chromatic number. But the factor 1/(2χ(G)) seems to be not best possible, for example, Radcliffe and Scott (Discrete Math 275-279, 1995) proved c=23 for trees, Berman et al. (Aust J Comb 81-85, 1997) showed that c=25 for graphs with maximum degree 3, so it is interesting to determine the exact value of c for special family of graphs. In this paper, we further confirm the conjecture for graphs with treewidth at most 2 with c=25, and the bound is best possible. [ABSTRACT FROM AUTHOR]

The total distance or Wiener index W ( G ) of a connected graph G is defined as the sum of distances between all pairs of vertices in G . In 1991, Šoltés posed the problem of finding all graphs G such that the equality W ( G ) = W ( G − v ) holds for all their vertices v . Up to now, the only known graph with this property is the cycle C 11 . Our main object of study is a relaxed version of this problem: Find graphs for which total distance does not change when a particular vertex is removed. We show that there are infinitely many graphs that satisfy this property. This gives hope that Šoltes's problem may have also some solutions distinct from C 11 . [ABSTRACT FROM AUTHOR]

In this paper we study some variants of Dirac-type problems in hypergraphs. First, we show that for k ≥ 3, if H is a k-graph on n ∊ kN vertices with independence number at most n=p and minimum codegree at least (1=p + o(1))n, where p is the smallest prime factor of k, then H contains a perfect matching. Second, we show that if H is a 3-graph on n ∊ 3N vertices which does not contain any induced copy of K4- (the unique 3-graph with 4 vertices and 3 edges) and has minimum codegree at least (1/3 + o(1)))n, then H contains a perfect matching. Moreover, if we allow the matching to miss at most 3 vertices, then the minimum degree condition can be reduced to (1/6+o(1)))n. Third, we show that if H is a 3-graph on n ∊ 4N vertices which does not contain any induced copy of K4- and has minimum codegree at least (1/8 + o(1)))n, then H contains a perfect Y-tiling, where Y represents the unique 3-graph with 4 vertices and 2 edges. We also provide the examples showing that our minimum codegree conditions are asymptotically best possible. Our main tool for finding the perfect matching is a characterization theorem in [J. Han, Trans. Amer. Math. Soc., 369 (2017), pp. 5197{5218] that characterizes the k-graphs with minimum codegree at least n/k which contain a perfect matching. [ABSTRACT FROM AUTHOR]

The Wiener index W ( G ) of a connected graph G is defined to be the sum of distances between all pairs of vertices in G . In 1991, Šoltés studied changes of the Wiener index caused by removing a single vertex. He posed the problem of finding all graphs G so that equality W ( G ) = W ( G − v ) holds for all their vertices v . The cycle with 11 vertices is still the only known graph with this property. In this paper we study a relaxed version of this problem and find graphs which Wiener index does not change when a particular vertex v is removed. We show that there is a unicyclic graph G on n vertices with W ( G ) = W ( G − v ) if and only if n ≥ 9 . Also, there is a unicyclic graph G with a cycle of length c for which W ( G ) = W ( G − v ) if and only if c ≥ 5 . Moreover, we show that every graph G is an induced subgraph of H such that W ( H ) = W ( H − v ) . As our relaxed version is rich with solutions, it gives hope that Šoltes’s problem may have also some solutions distinct from C 11 . [ABSTRACT FROM AUTHOR]

We discuss some problems related to induced subgraphs. (1) A good upper bound for the chromatic number in terms of the clique number for graphs in which every induced cycle has length 3 or 4. (2) The perfect chromatic number of a graph, which is the smallest number of perfect sets into which the vertex set of a graph can be partitioned. (A set of vertices is said to be perfect if it induces a perfect graph.) (3) Graphs in which the difference between the chromatic number and the clique number is at most one for every induced subgraph of the graph. (4) A weakening of the notorious Erdős–Hajnal conjecture. (5) A conjecture of Gyárfás about the χ -boundedness of a particular class of graphs. [ABSTRACT FROM AUTHOR]