Mining subgraphs with interesting structural properties from networks (or graphs) is a computationally challenging task. In this paper, we propose two algorithms for enumerating all connected induced subgraphs of a gi...Mining subgraphs with interesting structural properties from networks (or graphs) is a computationally challenging task. In this paper, we propose two algorithms for enumerating all connected induced subgraphs of a given cardinality from networks (or connected undirected graphs in networks). The first algorithm is a variant of a previous wellknown algorithm. The algorithm enumerates all connected induced subgraphs of cardinality k in a bottom-up manner. Thedata structures that lead to unit time element checking and linear space are presented. Different from previous algorithmsthat work in either a bottom-up manner or a reverse search manner, an algorithm that enumerates all connected inducedsubgraphs of cardinality k in a top-down manner is proposed. The correctness and complexity of the top-down algorithmare theoretically analyzed and proven. In the experiments, we evaluate the efficiency of the algorithms using a set of realworld networks from various fields. Experimental results show that the variant bottom-up algorithm outperforms thestate-of-the-art algorithms for enumerating connected induced subgraphs of small cardinality, and the top-down algorithmcan achieve an order of magnitude speedup over the state-of-the-art algorithms for enumerating connected induced subgraphs of large cardinality.展开更多
Given integers m and f,let Sn(m,f)be the set consisting of all integers e such that every n-vertex graph with e edges contains an m-vertex induced subgraph with f edges,and let σ(m,f)=lim sup_(n→∞)|S_(n)(m,f)|/(_(2...Given integers m and f,let Sn(m,f)be the set consisting of all integers e such that every n-vertex graph with e edges contains an m-vertex induced subgraph with f edges,and let σ(m,f)=lim sup_(n→∞)|S_(n)(m,f)|/(_(2)^(n)).As a natural extension of an extremal problem of Erdös,this was investigated by Erd˝os,Füredi,Rothschild and Sós 20 years ago.Their main result indicates that integers in S_(n)(m,f)are rare for most pairs(m,f),though they also found infinitely many pairs(m,f)whose σ(m,f)is a fixed positive constant.Here we aim to provide some improvements on this study.Our first result shows that σ(m,f)≤1/2 holds for all but finitely many pairs(m,f)and the constant 1/2 cannot be improved.This answers a question of Erdös et al.Our second result considers infinitely many pairs(m,f)of special forms,whose exact values of σ(m,f)were conjectured by Erdös et al.We partially solve this conjecture(only leaving two open cases)by making progress on some constructions which are related to number theory.Our proofs are based on the research of Erdös et al.and involve different arguments in number theory.We also discuss some related problems.展开更多
Let Gn,d be a random d-regular graph with n vertices, where d = o（n）. Given a fixed graph H, YH denotes the number of induced copies of H in Gn d In this paper, the authors determine the threshold of the event ＂YH ...Let Gn,d be a random d-regular graph with n vertices, where d = o（n）. Given a fixed graph H, YH denotes the number of induced copies of H in Gn d In this paper, the authors determine the threshold of the event ＂YH 〉 0＂, and also obtain the induced subgraph counts inside the threshold interval.展开更多
A graph is called claw-free if it contains no induced subgrapn lsomorpmc to K1,3. Matthews and Sumner proved that a 2-connected claw-free graph G is Hamiltonian if every vertex of it has degree at least （[V（G）I - 2...A graph is called claw-free if it contains no induced subgrapn lsomorpmc to K1,3. Matthews and Sumner proved that a 2-connected claw-free graph G is Hamiltonian if every vertex of it has degree at least （[V（G）I - 2）/3. At the workshop CSzC （Novy Smokovec, 1993）, Broersma conjectured the degree condition of this result can be restricted only to end-vertices of induced copies of N （the graph obtained from a triangle by adding three disjoint pendant edges）. Fujisawa and Yamashita showed that the degree condition of Matthews and Sumner can be restricted only to end-vertices of induced copies of Z1 （the graph obtained from a triangle by adding one pendant edge）. Our main result in this paper is a characterization of all graphs H such that a 2-connected claw-free graph G is Hamiltonian if eachend-vertex of every induced copy of H in G has degree at least IV（G）I/3 ＋ 1. This gives an affirmative solution of the conjecture of Broersma up to an additive constant.end-vertex of every induced copy of H in G has degree at least IV（G）I/3 ＋ 1. This gives an affirmative solution of the conjecture of Broersma up to an additive constant.展开更多
The definition of the ascending subgraph decomposition was given by Alavi. It has been conjectured that every graph of positive size has an ascending subgraph decomposition. In this paper it is proved that the regular...The definition of the ascending subgraph decomposition was given by Alavi. It has been conjectured that every graph of positive size has an ascending subgraph decomposition. In this paper it is proved that the regular graphs under some conditions do have an ascending subgraph decomposition.展开更多
In this paper,we survey known results on color-critical graphs in special graph classes.A graph is k-critical if its chromatic number is k but any proper subgraph of it has chromatic number less than k.For a family H ...In this paper,we survey known results on color-critical graphs in special graph classes.A graph is k-critical if its chromatic number is k but any proper subgraph of it has chromatic number less than k.For a family H of graphs,a graph is H-free if it does not contain H as an induced subgraph for every H∈H.A graph class is hereditary if it is H-free for some set H of graphs,and the graphs in H are called forbidden induced subgraphs for the class.We will focus on the characterization problem and the finiteness problem for hereditary graph classes that can be defined by one or two forbidden induced subgraphs.The characterization problem seeks a complete characterization of k-critical graphs in a given graph class and the finiteness problem asks if the number of k-critical graphs in a given class is finite.We shall survey results for both problems with an emphasis on how the results develop over the time and on the techniques used for proving results in the area.We also list important open problems and give some conjectures.展开更多
Two new hereditary classes of P 5-free graphs where the stability number can be found in polynomial time are proposed.They generalize several known results.
The traditional game of cops and robbers is played on undirected graph. Recently, the same game played on directed graph is getting attention by more and more people. We knew that if we forbid some subgraph we can bou...The traditional game of cops and robbers is played on undirected graph. Recently, the same game played on directed graph is getting attention by more and more people. We knew that if we forbid some subgraph we can bound the cop number of the corresponding class of graphs. In this paper, we analyze the game of cops and robbers on H^(-)-free digraphs. However, it is not the same as the case of undirected graph. So we give a new concept(H^(-)^(*)-free digraph) to get a similar conclusion about the case of undirected graph.展开更多
基金supported by the National Natural Science Foundation of China under Grant No.61404069the Scientific Research Project of Colleges and Universities in Guangdong Province of China under Grant No.2021ZDZX1027+1 种基金the Guangdong Basic and Applied Basic Research Foundation under Grant Nos.2022A1515110712 and 2023A1515010077the STU Scientific Research Foundation for Talents under Grant Nos.NTF20016 and NTF20017.
文摘Mining subgraphs with interesting structural properties from networks (or graphs) is a computationally challenging task. In this paper, we propose two algorithms for enumerating all connected induced subgraphs of a given cardinality from networks (or connected undirected graphs in networks). The first algorithm is a variant of a previous wellknown algorithm. The algorithm enumerates all connected induced subgraphs of cardinality k in a bottom-up manner. Thedata structures that lead to unit time element checking and linear space are presented. Different from previous algorithmsthat work in either a bottom-up manner or a reverse search manner, an algorithm that enumerates all connected inducedsubgraphs of cardinality k in a top-down manner is proposed. The correctness and complexity of the top-down algorithmare theoretically analyzed and proven. In the experiments, we evaluate the efficiency of the algorithms using a set of realworld networks from various fields. Experimental results show that the variant bottom-up algorithm outperforms thestate-of-the-art algorithms for enumerating connected induced subgraphs of small cardinality, and the top-down algorithmcan achieve an order of magnitude speedup over the state-of-the-art algorithms for enumerating connected induced subgraphs of large cardinality.
基金supported by Hong Kong RGC Grant GRF 16308219 and Hong Kong RGC Grant ECS 26304920supported by the National Key R and D Program of China 2020YFA0713100+4 种基金National Natural Science Foundation of China Grant 12125106Innovation Program for Quantum Science and Technology 2021ZD0302904Anhui Initiative in Quantum Information Technologies Grant AHY150200Research supported in part by NSFC Grant 11922113National Key Research and Development Program of China 2021YFA1000700.
文摘Given integers m and f,let Sn(m,f)be the set consisting of all integers e such that every n-vertex graph with e edges contains an m-vertex induced subgraph with f edges,and let σ(m,f)=lim sup_(n→∞)|S_(n)(m,f)|/(_(2)^(n)).As a natural extension of an extremal problem of Erdös,this was investigated by Erd˝os,Füredi,Rothschild and Sós 20 years ago.Their main result indicates that integers in S_(n)(m,f)are rare for most pairs(m,f),though they also found infinitely many pairs(m,f)whose σ(m,f)is a fixed positive constant.Here we aim to provide some improvements on this study.Our first result shows that σ(m,f)≤1/2 holds for all but finitely many pairs(m,f)and the constant 1/2 cannot be improved.This answers a question of Erdös et al.Our second result considers infinitely many pairs(m,f)of special forms,whose exact values of σ(m,f)were conjectured by Erdös et al.We partially solve this conjecture(only leaving two open cases)by making progress on some constructions which are related to number theory.Our proofs are based on the research of Erdös et al.and involve different arguments in number theory.We also discuss some related problems.
基金This research is supported by the National Natural Science of Foundation under Grant Nos.10531070 and 10721101 of China.
文摘Let Gn,d be a random d-regular graph with n vertices, where d = o（n）. Given a fixed graph H, YH denotes the number of induced copies of H in Gn d In this paper, the authors determine the threshold of the event ＂YH 〉 0＂, and also obtain the induced subgraph counts inside the threshold interval.
基金Supported by NSFC(Grant Nos.11271300 and 11571135)the project NEXLIZ–CZ.1.07/2.3.00/30.0038+1 种基金the project P202/12/G061 of the Czech Science Foundation and by the European Regional Development Fund(ERDF)the project NTIS-New Technologies for Information Society,European Centre of Excellence,CZ.1.05/1.1.00/02.0090
文摘A graph is called claw-free if it contains no induced subgrapn lsomorpmc to K1,3. Matthews and Sumner proved that a 2-connected claw-free graph G is Hamiltonian if every vertex of it has degree at least （[V（G）I - 2）/3. At the workshop CSzC （Novy Smokovec, 1993）, Broersma conjectured the degree condition of this result can be restricted only to end-vertices of induced copies of N （the graph obtained from a triangle by adding three disjoint pendant edges）. Fujisawa and Yamashita showed that the degree condition of Matthews and Sumner can be restricted only to end-vertices of induced copies of Z1 （the graph obtained from a triangle by adding one pendant edge）. Our main result in this paper is a characterization of all graphs H such that a 2-connected claw-free graph G is Hamiltonian if eachend-vertex of every induced copy of H in G has degree at least IV（G）I/3 ＋ 1. This gives an affirmative solution of the conjecture of Broersma up to an additive constant.end-vertex of every induced copy of H in G has degree at least IV（G）I/3 ＋ 1. This gives an affirmative solution of the conjecture of Broersma up to an additive constant.
文摘The definition of the ascending subgraph decomposition was given by Alavi. It has been conjectured that every graph of positive size has an ascending subgraph decomposition. In this paper it is proved that the regular graphs under some conditions do have an ascending subgraph decomposition.
文摘In this paper,we survey known results on color-critical graphs in special graph classes.A graph is k-critical if its chromatic number is k but any proper subgraph of it has chromatic number less than k.For a family H of graphs,a graph is H-free if it does not contain H as an induced subgraph for every H∈H.A graph class is hereditary if it is H-free for some set H of graphs,and the graphs in H are called forbidden induced subgraphs for the class.We will focus on the characterization problem and the finiteness problem for hereditary graph classes that can be defined by one or two forbidden induced subgraphs.The characterization problem seeks a complete characterization of k-critical graphs in a given graph class and the finiteness problem asks if the number of k-critical graphs in a given class is finite.We shall survey results for both problems with an emphasis on how the results develop over the time and on the techniques used for proving results in the area.We also list important open problems and give some conjectures.
基金The first author was supported by DIMACS Summer2 0 0 3Award
文摘Two new hereditary classes of P 5-free graphs where the stability number can be found in polynomial time are proposed.They generalize several known results.
文摘The traditional game of cops and robbers is played on undirected graph. Recently, the same game played on directed graph is getting attention by more and more people. We knew that if we forbid some subgraph we can bound the cop number of the corresponding class of graphs. In this paper, we analyze the game of cops and robbers on H^(-)-free digraphs. However, it is not the same as the case of undirected graph. So we give a new concept(H^(-)^(*)-free digraph) to get a similar conclusion about the case of undirected graph.
