A dominating induced matching(DIM)of G is an induced matching that dominates every edge of G.In this note,we completely determine the number of DIMs in the generalized Petersen graph P(n,k).We prove that if P(n,k)is a...A dominating induced matching(DIM)of G is an induced matching that dominates every edge of G.In this note,we completely determine the number of DIMs in the generalized Petersen graph P(n,k).We prove that if P(n,k)is a generalized Petersen graph with n=0(mod 5)and k=2,3(mod 5),then E(P(n,k))can be partitioned into five DIMs.Meanwhile,in the left cases k=0,1,4(mod 5),we build some counterexamples to show that there exist some P(n,k)'s which are DIM-free.展开更多
Let G be a connected graph having a perfect matching.The graph G is said to be induced matching(IM)extendable if every induced matching M of G is contained in a perfect matching of G.In this paper,we show that Halin g...Let G be a connected graph having a perfect matching.The graph G is said to be induced matching(IM)extendable if every induced matching M of G is contained in a perfect matching of G.In this paper,we show that Halin graph G=T∪C is IM-extendable if and only if its characteristic tree T is isomorphic to K_(1,3),K_(1,5),K_(1,7) or S_(2,2).展开更多
The induced matching partition number of graph G is the minimum integer k such that there exists a k-partition(V1,V2,…,Vk) of V(G)such that,for each i(1≤i≤k),G[Vi] is 1-regular.In this paper,we study the induced m...The induced matching partition number of graph G is the minimum integer k such that there exists a k-partition(V1,V2,…,Vk) of V(G)such that,for each i(1≤i≤k),G[Vi] is 1-regular.In this paper,we study the induced matching partition number of product graphs.We provide a lower bound and an upper bound for the induced matching partition number of product graphs,and exact results are given for some special product graphs.展开更多
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.展开更多
It is said that a graph G is independent-set-deletable factor-critical （in short, ID-factor-critical）, if, for everyindependent-set I which has the same parity as ｜V（G）｜, G - I has a perfect matching. A graph G ...It is said that a graph G is independent-set-deletable factor-critical （in short, ID-factor-critical）, if, for everyindependent-set I which has the same parity as ｜V（G）｜, G - I has a perfect matching. A graph G is strongly IM-extendable, if for every spanning supergraph H of G, every induced matching of H is included in a perfect matching of H. The κ-th power of G, denoted by G^κ, is the graph with vertex set V（G） in which two vertices are adjacent if and only if they have distance at most k in G. ID-factor-criticality and IM-extendability of power graphs are discussed in this article. The author shows that, if G is a connected graph, then G^3 and T（G） （the total graph of G） are ID-factor-critical, and G^4 （when ｜V（G）｜ is even） is strongly IM-extendable; if G is 2-connected, then D^2 is ID-factor-critical.展开更多
A k-tree of a connected graph G is a spanning tree with maximum degree at most k. The rupture degree for a connected graph G is defined by , where and , respectively, denote the order of the largest component and numb...A k-tree of a connected graph G is a spanning tree with maximum degree at most k. The rupture degree for a connected graph G is defined by , where and , respectively, denote the order of the largest component and number of components in . In this paper, we show that for a connected graph G, if for any cut-set , then G has a k-tree.展开更多
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.
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.展开更多
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.展开更多
目的:利用文献计量学方法对近10年铜死亡相关的国内外文献进行可视化分析,以便更好地了解铜死亡的研究进展,寻找潜在的研究方向。方法:以中国知网、万方、Web of Science核心数据库为数据来源,使用CiteSpace软件对2014年1月1日~2024年9...目的:利用文献计量学方法对近10年铜死亡相关的国内外文献进行可视化分析,以便更好地了解铜死亡的研究进展,寻找潜在的研究方向。方法:以中国知网、万方、Web of Science核心数据库为数据来源,使用CiteSpace软件对2014年1月1日~2024年9月30日有关铜死亡研究的相关文献进行发文量、国家、作者、机构和关键词的可视化分析。结果:铜死亡发文量近几年迅速增加,中国在发文数量上居首位,但中心性低于二、三名,即美国和印度;国内发文量前4的作者是王议贤、曹建平、焦旸、朱巍;机构间合作较少;热点话题主要集中在细胞凋亡、自噬、氧化应激等机制和相关疾病的探索上;神经退行性疾病和癌症是与铜死亡密切相关的疾病。结论:早期铜死亡发病机制的研究是铜死亡机制研究领域的热点,后期逐渐呈现出发病机制与临床疾病并行研究的趋势。展开更多
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.展开更多
A matching M of a graph G is an induced matching if no two edges in M arejoined by an edge of G.Let iz(G) denote the total number of induced matchings of G,named iz-index.It is well known that the Hosoya index of a gr...A matching M of a graph G is an induced matching if no two edges in M arejoined by an edge of G.Let iz(G) denote the total number of induced matchings of G,named iz-index.It is well known that the Hosoya index of a graph is the total number of matchings and the Hosoya index of a path can be calculated by the Fibonacci sequence.In this paper,we investigate the iz-index of graphs by using the Fibonacci-Narayana sequence and characterize some types of graphs with minimum and maximum iz-index,respectively.展开更多
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.展开更多
基金Ming Chen was supported by National Key Research and Development Program of China(No.2024YFA1013900)。
文摘A dominating induced matching(DIM)of G is an induced matching that dominates every edge of G.In this note,we completely determine the number of DIMs in the generalized Petersen graph P(n,k).We prove that if P(n,k)is a generalized Petersen graph with n=0(mod 5)and k=2,3(mod 5),then E(P(n,k))can be partitioned into five DIMs.Meanwhile,in the left cases k=0,1,4(mod 5),we build some counterexamples to show that there exist some P(n,k)'s which are DIM-free.
基金Supported by the National Natural Science Foundation of China(Grant Nos.61702291,11801371)Key Research Project in Universities of Henan Province(Grant No.21B110004)。
文摘Let G be a connected graph having a perfect matching.The graph G is said to be induced matching(IM)extendable if every induced matching M of G is contained in a perfect matching of G.In this paper,we show that Halin graph G=T∪C is IM-extendable if and only if its characteristic tree T is isomorphic to K_(1,3),K_(1,5),K_(1,7) or S_(2,2).
文摘The induced matching partition number of graph G is the minimum integer k such that there exists a k-partition(V1,V2,…,Vk) of V(G)such that,for each i(1≤i≤k),G[Vi] is 1-regular.In this paper,we study the induced matching partition number of product graphs.We provide a lower bound and an upper bound for the induced matching partition number of product graphs,and exact results are given for some special product graphs.
基金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.
基金Project supported by NSFC(10371112)NSFHN (0411011200)SRF for ROCS,SEM
文摘It is said that a graph G is independent-set-deletable factor-critical （in short, ID-factor-critical）, if, for everyindependent-set I which has the same parity as ｜V（G）｜, G - I has a perfect matching. A graph G is strongly IM-extendable, if for every spanning supergraph H of G, every induced matching of H is included in a perfect matching of H. The κ-th power of G, denoted by G^κ, is the graph with vertex set V（G） in which two vertices are adjacent if and only if they have distance at most k in G. ID-factor-criticality and IM-extendability of power graphs are discussed in this article. The author shows that, if G is a connected graph, then G^3 and T（G） （the total graph of G） are ID-factor-critical, and G^4 （when ｜V（G）｜ is even） is strongly IM-extendable; if G is 2-connected, then D^2 is ID-factor-critical.
文摘A k-tree of a connected graph G is a spanning tree with maximum degree at most k. The rupture degree for a connected graph G is defined by , where and , respectively, denote the order of the largest component and number of components in . In this paper, we show that for a connected graph G, if for any cut-set , then G has a k-tree.
基金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.
文摘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 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.
文摘目的:利用文献计量学方法对近10年铜死亡相关的国内外文献进行可视化分析,以便更好地了解铜死亡的研究进展,寻找潜在的研究方向。方法:以中国知网、万方、Web of Science核心数据库为数据来源,使用CiteSpace软件对2014年1月1日~2024年9月30日有关铜死亡研究的相关文献进行发文量、国家、作者、机构和关键词的可视化分析。结果:铜死亡发文量近几年迅速增加,中国在发文数量上居首位,但中心性低于二、三名,即美国和印度;国内发文量前4的作者是王议贤、曹建平、焦旸、朱巍;机构间合作较少;热点话题主要集中在细胞凋亡、自噬、氧化应激等机制和相关疾病的探索上;神经退行性疾病和癌症是与铜死亡密切相关的疾病。结论:早期铜死亡发病机制的研究是铜死亡机制研究领域的热点,后期逐渐呈现出发病机制与临床疾病并行研究的趋势。
基金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.
基金supported by the Science and Technology Program of Guangzhou,China (No.202002030183)by the Qinghai Province Natural Science Foundation (No.2020-ZJ-924)by the Guangdong Province Natural Science Foundationauthorized in 2020。
文摘A matching M of a graph G is an induced matching if no two edges in M arejoined by an edge of G.Let iz(G) denote the total number of induced matchings of G,named iz-index.It is well known that the Hosoya index of a graph is the total number of matchings and the Hosoya index of a path can be calculated by the Fibonacci sequence.In this paper,we investigate the iz-index of graphs by using the Fibonacci-Narayana sequence and characterize some types of graphs with minimum and maximum iz-index,respectively.
基金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.
