The aim of this paper is to given an algebraic computational method for finding maximal independent sets as well as the independent number of an arbitrary finite graph of n vertices G by strengthening the problem of f...The aim of this paper is to given an algebraic computational method for finding maximal independent sets as well as the independent number of an arbitrary finite graph of n vertices G by strengthening the problem of finding maximal independent sets of G to the problem of finding k-independent sets in G for. It is shown that the existence of k-independent sets in G is equivalent to the existence of solutions of a system of multivariate polynomial equations. It follows that the problem of finding k-independent sets can be realized by using Gröbner bases of polynomial ideals. Since the number of k-independent sets is finite, the triangular equations composed by Gröbner bases are easier to be solved. Consequently, the maximal independent sets and the independent number of G are obtained after solving at most n such equations. Finally, the numerical example is presented to illustrate the effectiveness of this algebraic computational method.展开更多
Let G be a graph,for any u∈V(G),let N(u) denote the neighborhood of u and d(u)=|N(u)| be the degree of u.For any UV(G),let N(U)=∪_~u∈U N(u), and d(U)=|N(U)|.A graph G is called claw-free if it has no induced subgra...Let G be a graph,for any u∈V(G),let N(u) denote the neighborhood of u and d(u)=|N(u)| be the degree of u.For any UV(G),let N(U)=∪_~u∈U N(u), and d(U)=|N(U)|.A graph G is called claw-free if it has no induced subgraph isomorphic to K_~1,3 .One of the fundamental results concerning cycles in claw-free graphs is due to Tian Feng,et al.: Let G be a 2-connected claw-free graph of order n,and d(u)+d(v)+d(w)≥n-2 for every independent vertex set {u,v,w} of G, then G is Hamiltonian. It is proved that,for any three positive integers s,t and w,such that if G is a (s+t+w-1)-connected claw-free graph of order n,and d(S)+d(T)+d(W)>n-(s+t+w) for every three disjoint independent vertex sets S,T,W with |S|=s,|T|=t,|W|=w,and S∪T∪W is also independent,then G is Hamiltonian.Other related results are obtained too.展开更多
G. C. Ying, Y. Y. Meng, B. E. Sagan, and V. R. Vatter [1] found the maximum number of maximal independent sets in connected graphs which contain at most two cycles. In this paper, we give an alternative proof to deter...G. C. Ying, Y. Y. Meng, B. E. Sagan, and V. R. Vatter [1] found the maximum number of maximal independent sets in connected graphs which contain at most two cycles. In this paper, we give an alternative proof to determine the largest number of maximal independent sets among all connected graphs of order n ≥ 12, which contain at most two cycles. We also characterize the extremal graph achieving this maximum value.展开更多
The paper discusses an enhancement to a recently presented supervised learning algorithm to solve the Maximum Independent Set problem.In particular,it is shown that the algorithm can be improved by simplifying the tas...The paper discusses an enhancement to a recently presented supervised learning algorithm to solve the Maximum Independent Set problem.In particular,it is shown that the algorithm can be improved by simplifying the task learnt by the neural network adopted,with measurable effects on the quality of the solutions provided on unseen instances.Empirical results are presented to validate the idea..展开更多
A path-factor is a spanning subgraph F of G such that every component of F is a path with at least two vertices.Let k≥2 be an integer.A P_(≥k)-factor of G means a path factor in which each component is a path with a...A path-factor is a spanning subgraph F of G such that every component of F is a path with at least two vertices.Let k≥2 be an integer.A P_(≥k)-factor of G means a path factor in which each component is a path with at least k vertices.A graph G is a P_(≥k)-factor covered graph if for any e∈E(G),G has a P_(≥k)-factor including e.Letβbe a real number with 1/3≤β≤1 and k be a positive integer.We verify that(ⅰ)a k-connected graph G of order n with n≥5k+2 has a P_(≥3)-factor if|NG(I)|>β(n-3k-1)+k for every independent set I of G with|I|=「β(2k+1)」;(ⅱ)a(k+1)-connected graph G of order n with n≥5k+2 is a P_(≥3)-factor covered graph if|NG(I)|>β(n-3k-1)+k+1 for every independent set I of G with|I|=「β(2k+1)」.展开更多
The partition problem of a given graph into three independent sets of minimizing the maximum one is studied in this paper.This problem is NP-hard,even restricted to bipartite graphs.First,a simple 3/2-approximation al...The partition problem of a given graph into three independent sets of minimizing the maximum one is studied in this paper.This problem is NP-hard,even restricted to bipartite graphs.First,a simple 3/2-approximation algorithm for any 2-colorable graph is presented.An improved 7/5-approximation algorithm is then designed for a tree.The theoretical proof of the improved algorithm performance ratio is constructive,thus providing an explicit partition approach for each case according to the cardinality of two color classes.展开更多
A subset I of vertices of an undirected connected graph G is a nonseparating independent set(NSIS)if no two vertices of I are adjacent and GI is connected.Let Z(G)denote the cardinality of a maximum NSIS of G.A nonsep...A subset I of vertices of an undirected connected graph G is a nonseparating independent set(NSIS)if no two vertices of I are adjacent and GI is connected.Let Z(G)denote the cardinality of a maximum NSIS of G.A nonseparating independent set containing Z(G)vertices is called the maximum nonseparating independent set.In this paper,we firstly give an upper bound for Z(G)of regular graphs and determine Z(G)for some types of circular graphs.Secondly,we show a relationship between Z(G)and the maximum genus M(G)of a general graph.Finally,an important formula is provided to compute Z(G),i.e.,Z(G)=Σx∈I dI(x)+2(M(G-I)-γM(G))+(ξ(G-I)-ξ(G));where I is the maximum nonseparating independent set and ξ(G)is the Betti deficiency(Xuong,1979)of G.展开更多
A channel allocation algorithm based on the maximum independent set is proposed to decrease network conflict and improve network performance. First, a channel allocation model is formulated and a series of the maximum...A channel allocation algorithm based on the maximum independent set is proposed to decrease network conflict and improve network performance. First, a channel allocation model is formulated and a series of the maximum independent sets (MISs) are obtained from a contention graph by the proposed approximation algorithm with low complexity. Then, a weighted contention graph is obtained using the number of contention vertices between two MISs as a weighted value. Links are allocated to channels by the weighted contention graph to minimize conflicts between independent sets. Finally, after channel allocation, each node allocates network interface cards (NICs) to links that are allocated channels according to the queue lengths of NICs. Simulations are conducted to evaluate the proposed algorithm. The results show that the proposed algorithm significantly improves the network throughput and decreases the end to end delay.展开更多
In this paper, we consider the relationship between the binding number and the existence of fractional k-factors of graphs. The binding number of G is defined by Woodall as bind(G)=min{ | NG(X) || X |:∅≠X⊆V(G) }. It ...In this paper, we consider the relationship between the binding number and the existence of fractional k-factors of graphs. The binding number of G is defined by Woodall as bind(G)=min{ | NG(X) || X |:∅≠X⊆V(G) }. It is proved that a graph G has a fractional 1-factor if bind(G)≥1and has a fractional k-factor if bind(G)≥k−1k. Furthermore, it is showed that both results are best possible in some sense.展开更多
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.展开更多
Independent sets play an important role in matroid theory. In this paper, the definitions of pre-independent fuzzy set system and independent fuzzy set system in L-fuzzy setting are presented. Independent M-...Independent sets play an important role in matroid theory. In this paper, the definitions of pre-independent fuzzy set system and independent fuzzy set system in L-fuzzy setting are presented. Independent M-fuzzifying set system is introduced and some of its properties are discussed. Further independent (L,M)-fuzzy set system is given and some of its properties are obtained. The relations of these independent set systems in the setting of fuzzy vector spaces and fuzzy graphs are showed.展开更多
To cope with the constraint problem of power consumption and transmission delay in the virtual backbone of wireless sensor network, a distributed connected dominating set (CDS) algorithm with (α,β)-constraints i...To cope with the constraint problem of power consumption and transmission delay in the virtual backbone of wireless sensor network, a distributed connected dominating set (CDS) algorithm with (α,β)-constraints is proposed. Based on the (α, β)-tree concept, a new connected dominating tree with bounded transmission delay problem(CDTT) is defined and a corresponding algorithm is designed to construct a CDT-tree which can trade off limited total power and bounded transmission delay from source to destination nodes. The CDT algorithm consists of two phases: The first phase constructs a maximum independent set(MIS)in a unit disk graph model. The second phase estimates the distance and calculates the transmission power to construct a spanning tree in an undirected graph with different weights for MST and SPF, respectively. The theoretical analysis and simulation results show that the CDT algorithm gives a correct solution to the CDTF problem and forms a virtual backbone with( α,β)-constraints balancing the requirements of power consumption and transmission delay.展开更多
Let G be a 2 connected graph with n vertices. In this paper, we prove that if there exist two vertices of any there independent vertices in G such that the sum of whose degree is at least n , then G ...Let G be a 2 connected graph with n vertices. In this paper, we prove that if there exist two vertices of any there independent vertices in G such that the sum of whose degree is at least n , then G is pancyclic, or G is K n/2,n/2 , or G is K n/2,n/2 -e , or G is a cycle of length 5.展开更多
This paper deals with the representation of the solutions of a polynomial system, and concentrates on the high-dimensional case. Based on the rational univari- ate representation of zero-dimensional polynomial systems...This paper deals with the representation of the solutions of a polynomial system, and concentrates on the high-dimensional case. Based on the rational univari- ate representation of zero-dimensional polynomial systems, we give a new description called rational representation for the solutions of a high-dimensional polynomial sys- tem and propose an algorithm for computing it. By this way all the solutions of any high-dimensional polynomial system can be represented by a set of so-called rational- representation sets.展开更多
Let G be a 2 connected simple graph of order n and connectivity k .Bauer, Broersma and Li proved that for an independent set S=u,v,w, d(u)+d(v)+d(w)≥n+k ,then G is Hamiltonian. This paper improves ...Let G be a 2 connected simple graph of order n and connectivity k .Bauer, Broersma and Li proved that for an independent set S=u,v,w, d(u)+d(v)+d(w)≥n+k ,then G is Hamiltonian. This paper improves the result.Let S be an independent set. If there exist u,v∈S,du,v=2, then S is called a 2 independent set. This paper proves the following result. Let G be a simple graph of order n and connectivity k≥2 . If for every 2 independent set S=u,v,w, d(u)+d(v)+d(w)≥n+k , then G is Hamiltonian. This result implies that we may consider all triples of 2 independent set instead of all triples of independent set.展开更多
For a simple connected graph G, let A(G) and Q(G) be the adjacency matrix and signless Laplacian matrix, respectively of G. The principal eigenvector of A(G)(resp.Q(G)) is the unit positive eigenvector corresponding t...For a simple connected graph G, let A(G) and Q(G) be the adjacency matrix and signless Laplacian matrix, respectively of G. The principal eigenvector of A(G)(resp.Q(G)) is the unit positive eigenvector corresponding to the largest eigenvalue of A(G)(resp. Q(G)). In this paper, an upper bound and lower bound for the sum of the squares of the entries of the principal eigenvector of Q(G) corresponding to the vertices of an independent set are obtained.展开更多
The minimum independent dominance set(MIDS)problem is an important version of the dominating set with some other applications.In this work,we present an improved master-apprentice evolutionary algorithm for solving th...The minimum independent dominance set(MIDS)problem is an important version of the dominating set with some other applications.In this work,we present an improved master-apprentice evolutionary algorithm for solving the MIDS problem based on a path-breaking strategy called MAE-PB.The proposed MAE-PB algorithm combines a construction function for the initial solution generation and candidate solution restarting.It is a multiple neighborhood-based local search algorithm that improves the quality of the solution using a path-breaking strategy for solution recombination based on master and apprentice solutions and a perturbation strategy for disturbing the solution when the algorithm cannot improve the solution quality within a certain number of steps.We show the competitiveness of the MAE-PB algorithm by presenting the computational results on classical benchmarks from the literature and a suite of massive graphs from real-world applications.The results show that the MAE-PB algorithm achieves high performance.In particular,for the classical benchmarks,the MAE-PB algorithm obtains the best-known results for seven instances,whereas for several massive graphs,it improves the best-known results for 62 instances.We investigate the proposed key ingredients to determine their impact on the performance of the proposed algorithm.展开更多
In this paper,we present the concept of Banach-mean equicontinuity and prove that the Banach-,Weyl-and Besicovitch-mean equicontinuities of a dynamic system of Abelian group action are equivalent.Furthermore,we obtain...In this paper,we present the concept of Banach-mean equicontinuity and prove that the Banach-,Weyl-and Besicovitch-mean equicontinuities of a dynamic system of Abelian group action are equivalent.Furthermore,we obtain that the topological entropy of a transitive,almost Banach-mean equicontinuous dynamical system of Abelian group action is zero.As an application of our main result,we show that the topological entropy of the Banach-mean equicontinuous system under the action of an Abelian groups is zero.展开更多
The minimum vertex cover problem(MVCP)is a well-known combinatorial optimization problem of graph theory.The MVCP is an NP(nondeterministic polynomial)complete problem and it has an exponential growing complexity with...The minimum vertex cover problem(MVCP)is a well-known combinatorial optimization problem of graph theory.The MVCP is an NP(nondeterministic polynomial)complete problem and it has an exponential growing complexity with respect to the size of a graph.No algorithm exits till date that can exactly solve the problem in a deterministic polynomial time scale.However,several algorithms are proposed that solve the problem approximately in a short polynomial time scale.Such algorithms are useful for large size graphs,for which exact solution of MVCP is impossible with current computational resources.The MVCP has a wide range of applications in the fields like bioinformatics,biochemistry,circuit design,electrical engineering,data aggregation,networking,internet traffic monitoring,pattern recognition,marketing and franchising etc.This work aims to solve the MVCP approximately by a novel graph decomposition approach.The decomposition of the graph yields a subgraph that contains edges shared by triangular edge structures.A subgraph is covered to yield a subgraph that forms one or more Hamiltonian cycles or paths.In order to reduce complexity of the algorithm a new strategy is also proposed.The reduction strategy can be used for any algorithm solving MVCP.Based on the graph decomposition and the reduction strategy,two algorithms are formulated to approximately solve the MVCP.These algorithms are tested using well known standard benchmark graphs.The key feature of the results is a good approximate error ratio and improvement in optimum vertex cover values for few graphs.展开更多
Let G be a 3-connected graph with n vertices. The paper proves that if for each pair of vertices u and v of G, d(u,v)=2, has |N(u)∩N(v)|≤α(α is the minimum independent set number), and then max{d(u),d(v)}≥n+12,...Let G be a 3-connected graph with n vertices. The paper proves that if for each pair of vertices u and v of G, d(u,v)=2, has |N(u)∩N(v)|≤α(α is the minimum independent set number), and then max{d(u),d(v)}≥n+12, then G is a Hamilton connected graph.展开更多
文摘The aim of this paper is to given an algebraic computational method for finding maximal independent sets as well as the independent number of an arbitrary finite graph of n vertices G by strengthening the problem of finding maximal independent sets of G to the problem of finding k-independent sets in G for. It is shown that the existence of k-independent sets in G is equivalent to the existence of solutions of a system of multivariate polynomial equations. It follows that the problem of finding k-independent sets can be realized by using Gröbner bases of polynomial ideals. Since the number of k-independent sets is finite, the triangular equations composed by Gröbner bases are easier to be solved. Consequently, the maximal independent sets and the independent number of G are obtained after solving at most n such equations. Finally, the numerical example is presented to illustrate the effectiveness of this algebraic computational method.
文摘Let G be a graph,for any u∈V(G),let N(u) denote the neighborhood of u and d(u)=|N(u)| be the degree of u.For any UV(G),let N(U)=∪_~u∈U N(u), and d(U)=|N(U)|.A graph G is called claw-free if it has no induced subgraph isomorphic to K_~1,3 .One of the fundamental results concerning cycles in claw-free graphs is due to Tian Feng,et al.: Let G be a 2-connected claw-free graph of order n,and d(u)+d(v)+d(w)≥n-2 for every independent vertex set {u,v,w} of G, then G is Hamiltonian. It is proved that,for any three positive integers s,t and w,such that if G is a (s+t+w-1)-connected claw-free graph of order n,and d(S)+d(T)+d(W)>n-(s+t+w) for every three disjoint independent vertex sets S,T,W with |S|=s,|T|=t,|W|=w,and S∪T∪W is also independent,then G is Hamiltonian.Other related results are obtained too.
文摘G. C. Ying, Y. Y. Meng, B. E. Sagan, and V. R. Vatter [1] found the maximum number of maximal independent sets in connected graphs which contain at most two cycles. In this paper, we give an alternative proof to determine the largest number of maximal independent sets among all connected graphs of order n ≥ 12, which contain at most two cycles. We also characterize the extremal graph achieving this maximum value.
基金supported by the Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung(CH)(No.200020-182360)。
文摘The paper discusses an enhancement to a recently presented supervised learning algorithm to solve the Maximum Independent Set problem.In particular,it is shown that the algorithm can be improved by simplifying the task learnt by the neural network adopted,with measurable effects on the quality of the solutions provided on unseen instances.Empirical results are presented to validate the idea..
文摘A path-factor is a spanning subgraph F of G such that every component of F is a path with at least two vertices.Let k≥2 be an integer.A P_(≥k)-factor of G means a path factor in which each component is a path with at least k vertices.A graph G is a P_(≥k)-factor covered graph if for any e∈E(G),G has a P_(≥k)-factor including e.Letβbe a real number with 1/3≤β≤1 and k be a positive integer.We verify that(ⅰ)a k-connected graph G of order n with n≥5k+2 has a P_(≥3)-factor if|NG(I)|>β(n-3k-1)+k for every independent set I of G with|I|=「β(2k+1)」;(ⅱ)a(k+1)-connected graph G of order n with n≥5k+2 is a P_(≥3)-factor covered graph if|NG(I)|>β(n-3k-1)+k+1 for every independent set I of G with|I|=「β(2k+1)」.
基金gment This work was supported by the National Natural Science Foundation of China(No.11971139)the Natural Science Foundation of Zhejiang Province(No.LY21A010014)the Fundamental Research Funds for the Provincial Universities of Zhejiang(No.GK22990929900)。
文摘The partition problem of a given graph into three independent sets of minimizing the maximum one is studied in this paper.This problem is NP-hard,even restricted to bipartite graphs.First,a simple 3/2-approximation algorithm for any 2-colorable graph is presented.An improved 7/5-approximation algorithm is then designed for a tree.The theoretical proof of the improved algorithm performance ratio is constructive,thus providing an explicit partition approach for each case according to the cardinality of two color classes.
基金supported by the National Natural Science Foundation of China(Nos.11171114,11401576,61662066,62072296)Science and Technology Commission of Shanghai Municipality(No.13dz2260400)。
文摘A subset I of vertices of an undirected connected graph G is a nonseparating independent set(NSIS)if no two vertices of I are adjacent and GI is connected.Let Z(G)denote the cardinality of a maximum NSIS of G.A nonseparating independent set containing Z(G)vertices is called the maximum nonseparating independent set.In this paper,we firstly give an upper bound for Z(G)of regular graphs and determine Z(G)for some types of circular graphs.Secondly,we show a relationship between Z(G)and the maximum genus M(G)of a general graph.Finally,an important formula is provided to compute Z(G),i.e.,Z(G)=Σx∈I dI(x)+2(M(G-I)-γM(G))+(ξ(G-I)-ξ(G));where I is the maximum nonseparating independent set and ξ(G)is the Betti deficiency(Xuong,1979)of G.
基金The National High Technology Research and Development Program of China(863 Program)(No.2013AA013601)Prospective Research Project on Future Netw orks of Jiangsu Future Netw orks Innovation Institute(No.BY2013095-1-18)
文摘A channel allocation algorithm based on the maximum independent set is proposed to decrease network conflict and improve network performance. First, a channel allocation model is formulated and a series of the maximum independent sets (MISs) are obtained from a contention graph by the proposed approximation algorithm with low complexity. Then, a weighted contention graph is obtained using the number of contention vertices between two MISs as a weighted value. Links are allocated to channels by the weighted contention graph to minimize conflicts between independent sets. Finally, after channel allocation, each node allocates network interface cards (NICs) to links that are allocated channels according to the queue lengths of NICs. Simulations are conducted to evaluate the proposed algorithm. The results show that the proposed algorithm significantly improves the network throughput and decreases the end to end delay.
文摘In this paper, we consider the relationship between the binding number and the existence of fractional k-factors of graphs. The binding number of G is defined by Woodall as bind(G)=min{ | NG(X) || X |:∅≠X⊆V(G) }. It is proved that a graph G has a fractional 1-factor if bind(G)≥1and has a fractional k-factor if bind(G)≥k−1k. Furthermore, it is showed that both results are best possible in some sense.
基金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.
文摘Independent sets play an important role in matroid theory. In this paper, the definitions of pre-independent fuzzy set system and independent fuzzy set system in L-fuzzy setting are presented. Independent M-fuzzifying set system is introduced and some of its properties are discussed. Further independent (L,M)-fuzzy set system is given and some of its properties are obtained. The relations of these independent set systems in the setting of fuzzy vector spaces and fuzzy graphs are showed.
基金Major Program of the National Natural Science Foundation of China (No.70533050)High Technology Research Program ofJiangsu Province(No.BG2007012)+1 种基金China Postdoctoral Science Foundation(No.20070411065)Science Foundation of China University of Mining andTechnology(No.OC080303)
文摘To cope with the constraint problem of power consumption and transmission delay in the virtual backbone of wireless sensor network, a distributed connected dominating set (CDS) algorithm with (α,β)-constraints is proposed. Based on the (α, β)-tree concept, a new connected dominating tree with bounded transmission delay problem(CDTT) is defined and a corresponding algorithm is designed to construct a CDT-tree which can trade off limited total power and bounded transmission delay from source to destination nodes. The CDT algorithm consists of two phases: The first phase constructs a maximum independent set(MIS)in a unit disk graph model. The second phase estimates the distance and calculates the transmission power to construct a spanning tree in an undirected graph with different weights for MST and SPF, respectively. The theoretical analysis and simulation results show that the CDT algorithm gives a correct solution to the CDTF problem and forms a virtual backbone with( α,β)-constraints balancing the requirements of power consumption and transmission delay.
文摘Let G be a 2 connected graph with n vertices. In this paper, we prove that if there exist two vertices of any there independent vertices in G such that the sum of whose degree is at least n , then G is pancyclic, or G is K n/2,n/2 , or G is K n/2,n/2 -e , or G is a cycle of length 5.
基金The National Grand Fundamental Research 973 Program (2004CB318000) of China
文摘This paper deals with the representation of the solutions of a polynomial system, and concentrates on the high-dimensional case. Based on the rational univari- ate representation of zero-dimensional polynomial systems, we give a new description called rational representation for the solutions of a high-dimensional polynomial sys- tem and propose an algorithm for computing it. By this way all the solutions of any high-dimensional polynomial system can be represented by a set of so-called rational- representation sets.
文摘Let G be a 2 connected simple graph of order n and connectivity k .Bauer, Broersma and Li proved that for an independent set S=u,v,w, d(u)+d(v)+d(w)≥n+k ,then G is Hamiltonian. This paper improves the result.Let S be an independent set. If there exist u,v∈S,du,v=2, then S is called a 2 independent set. This paper proves the following result. Let G be a simple graph of order n and connectivity k≥2 . If for every 2 independent set S=u,v,w, d(u)+d(v)+d(w)≥n+k , then G is Hamiltonian. This result implies that we may consider all triples of 2 independent set instead of all triples of independent set.
文摘For a simple connected graph G, let A(G) and Q(G) be the adjacency matrix and signless Laplacian matrix, respectively of G. The principal eigenvector of A(G)(resp.Q(G)) is the unit positive eigenvector corresponding to the largest eigenvalue of A(G)(resp. Q(G)). In this paper, an upper bound and lower bound for the sum of the squares of the entries of the principal eigenvector of Q(G) corresponding to the vertices of an independent set are obtained.
基金supported by the National Natural Science Foundation of China(Grant Nos.61806050,61972063,61976050)the Fundamental Research Funds for the Central Universities(2412020FZ030,2412019ZD013,2412019FZ051)Jilin Science and Technology Association(QT202005).
文摘The minimum independent dominance set(MIDS)problem is an important version of the dominating set with some other applications.In this work,we present an improved master-apprentice evolutionary algorithm for solving the MIDS problem based on a path-breaking strategy called MAE-PB.The proposed MAE-PB algorithm combines a construction function for the initial solution generation and candidate solution restarting.It is a multiple neighborhood-based local search algorithm that improves the quality of the solution using a path-breaking strategy for solution recombination based on master and apprentice solutions and a perturbation strategy for disturbing the solution when the algorithm cannot improve the solution quality within a certain number of steps.We show the competitiveness of the MAE-PB algorithm by presenting the computational results on classical benchmarks from the literature and a suite of massive graphs from real-world applications.The results show that the MAE-PB algorithm achieves high performance.In particular,for the classical benchmarks,the MAE-PB algorithm obtains the best-known results for seven instances,whereas for several massive graphs,it improves the best-known results for 62 instances.We investigate the proposed key ingredients to determine their impact on the performance of the proposed algorithm.
基金supported by NSF of China(11671057)NSF of Chongqing(cstc2020jcyj-msxmX0694)the Fundamental Research Funds for the Central Universities(2018CDQYST0023).
文摘In this paper,we present the concept of Banach-mean equicontinuity and prove that the Banach-,Weyl-and Besicovitch-mean equicontinuities of a dynamic system of Abelian group action are equivalent.Furthermore,we obtain that the topological entropy of a transitive,almost Banach-mean equicontinuous dynamical system of Abelian group action is zero.As an application of our main result,we show that the topological entropy of the Banach-mean equicontinuous system under the action of an Abelian groups is zero.
文摘The minimum vertex cover problem(MVCP)is a well-known combinatorial optimization problem of graph theory.The MVCP is an NP(nondeterministic polynomial)complete problem and it has an exponential growing complexity with respect to the size of a graph.No algorithm exits till date that can exactly solve the problem in a deterministic polynomial time scale.However,several algorithms are proposed that solve the problem approximately in a short polynomial time scale.Such algorithms are useful for large size graphs,for which exact solution of MVCP is impossible with current computational resources.The MVCP has a wide range of applications in the fields like bioinformatics,biochemistry,circuit design,electrical engineering,data aggregation,networking,internet traffic monitoring,pattern recognition,marketing and franchising etc.This work aims to solve the MVCP approximately by a novel graph decomposition approach.The decomposition of the graph yields a subgraph that contains edges shared by triangular edge structures.A subgraph is covered to yield a subgraph that forms one or more Hamiltonian cycles or paths.In order to reduce complexity of the algorithm a new strategy is also proposed.The reduction strategy can be used for any algorithm solving MVCP.Based on the graph decomposition and the reduction strategy,two algorithms are formulated to approximately solve the MVCP.These algorithms are tested using well known standard benchmark graphs.The key feature of the results is a good approximate error ratio and improvement in optimum vertex cover values for few graphs.
文摘Let G be a 3-connected graph with n vertices. The paper proves that if for each pair of vertices u and v of G, d(u,v)=2, has |N(u)∩N(v)|≤α(α is the minimum independent set number), and then max{d(u),d(v)}≥n+12, then G is a Hamilton connected graph.