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.展开更多
In Gao’s previous work, the authors determined several degree conditions of a graph which admits fractional factor in particular settings. It was revealed that these degree conditions are tight if b = f(x) = g(x) = a...In Gao’s previous work, the authors determined several degree conditions of a graph which admits fractional factor in particular settings. It was revealed that these degree conditions are tight if b = f(x) = g(x) = a for all vertices x in G. In this paper, we continue to discuss these degree conditions for admitting fractional factor in the setting that several vertices and edges are removed and there is a difference Δ between g(x) and f(x) for every vertex x in G. These obtained new degree conditions reformulate Gao’s previous conclusions, and show how Δ acts in the results. Furthermore,counterexamples are structured to reveal the sharpness of degree conditions in the setting f(x) =g(x) + Δ.展开更多
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.展开更多
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.展开更多
文摘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.
基金Supported by NSFC(Grant Nos.11761083,11771402 and 11671053)Fundacion Seneca(Spain)(Grant No.20783/PI/18)Ministry of Science,Innovation and Universities(Spain)(Grant No.PGC2018-097198-B-100)。
文摘In Gao’s previous work, the authors determined several degree conditions of a graph which admits fractional factor in particular settings. It was revealed that these degree conditions are tight if b = f(x) = g(x) = a for all vertices x in G. In this paper, we continue to discuss these degree conditions for admitting fractional factor in the setting that several vertices and edges are removed and there is a difference Δ between g(x) and f(x) for every vertex x in G. These obtained new degree conditions reformulate Gao’s previous conclusions, and show how Δ acts in the results. Furthermore,counterexamples are structured to reveal the sharpness of degree conditions in the setting f(x) =g(x) + Δ.
基金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 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.
