Solving the k-Independent Sets Problem of Graphs by Gröbner Bases

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.

NEIGHBORHOOD UNION OF INDEPENDENT SETS AND HAMILTONICITY OF CLAW-FREE GRAPHS

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.

An Alternative Proof of the Largest Number of Maximal Independent Sets in Connected Graphs Having at Most Two Cycles

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.

Maximum Independent Sets and Supervised Learning

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..

Path Factors and Neighborhoods of Independent Sets in Graphs

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)」.

Approximation Algorithms for Graph Partition into Bounded Independent Sets

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.

Nonseparating Independent Sets and Maximum Genus of Graphs

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 maximum-independent-set-based channel allocation algorithm for multi-channel wireless networks

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.

Binding Number and Fractional k-Factors of Graphs

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.

INDEPENDENT-SET-DELETABLE FACTOR-CRITICAL POWER GRAPHS

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.

The Study on the (L,M)-Fuzzy Independent Set Systems

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.

(α,β)-constraints connected dominating set algorithm in wireless sensor network

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.

New Vertex-Degree Condition for Pancyclic Graphs

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.

Computation of the Rational Representation for Solutions of High-dimensional 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.

Hamilton Graphs Involving Connectivity

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.

Some ResuIts on the Principal Eigenvector

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.

An improved master-apprentice evolutionary algorithm for minimum independent dominating set problem

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 SYSTEMS WITH ALMOST BANACH-MEAN EQUICONTINUITY FOR ABELIAN GROUP ACTIONS

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.

Vertex Cover Optimization Using a Novel Graph Decomposition Approach

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.

A Sufficient Condition of Hamilton Connected Graph

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.