The Pair Completion algorithm for the Homogeneous Set Sandwich Problem

A homogeneous set is a non-trivial module of a graph, i.e., a non-empty, non-unitary, proper vertex subset such that all its elements present the same outer neighborhood. Given two graphs G₁(V,E₁) and G₂(V,E₂), the Homogeneous Set Sandwich Problem (HSSP) asks whether there exists a graph GS(V,ES), E₁⊆ES⊆E₂, which has a homogeneous set. This paper presents an algorithm that uses the concept of bias graph [S. Tang, F. Yeh, Y. Wang, An efficient algorithm for solving the homogeneous set sandwich problem, Inform. Process. Lett. 77 (2001) 17-22] to solve the problem in time, thus outperforming the other known HSSP deterministic algorithms for inputs where .     

Weighted Coloring: further complexity and approximability results

Given a vertex-weighted graph G=(V,E;w), w(v)?0 for any v∈V, we consider a weighted version of the coloring problem which consists in finding a partition S=(S₁,…,Sk) of the vertex set of G into stable sets and minimizing where the weight of S is defined as . In this paper, we continue the investigation of the complexity and the approximability of this problem by answering some of the questions raised by Guan and Zhu [D.J. Guan, X. Zhu, A coloring problem for weighted graphs, Inform. Process. Lett. 61 (2) (1997) 77-81].     

Lucky labelings of graphs

Suppose the vertices of a graph G were labeled arbitrarily by positive integers, and let S(v) denote the sum of labels over all neighbors of vertex v. A labeling is lucky if the function S is a proper coloring of G, that is, if we have S(u)≠S(v) whenever u and v are adjacent. The least integer k for which a graph G has a lucky labeling from the set {1,2,…,k} is the lucky number of G, denoted by η(G).Using algebraic methods we prove that η(G)?k+1 for every bipartite graph G whose edges can be oriented so that the maximum out-degree of a vertex is at most k. In particular, we get that η(T)?2 for every tree T, and η(G)?3 for every bipartite planar graph G. By another technique we get a bound for the lucky number in terms of the acyclic chromatic number. This gives in particular that for every planar graph G. Nevertheless we offer a provocative conjecture that η(G)?χ(G) for every graph G.     

Super connectivity of Kronecker products of graphs

Let G₁ and G₂ be two connected graphs. The Kronecker product G₁×G₂ has vertex set V(G₁×G₂)=V(G₁)×V(G₂) and the edge set . In this paper, we show that if G is a bipartite graph with κ(G)=δ(G), then G×Kn(n?3) is super-κ.     

Restricted arc-connectivity of digraphs

Since interconnection networks are often modeled by graphs or digraphs, the edge-connectivity of a graph or arc-connectivity of a digraph are important measurements for fault tolerance of networks.The restricted edge-connectivity λ^′(G) of a graph G is the minimum cardinality over all edge-cuts S in a graph G such that there are no isolated vertices in G−S. A connected graph G is called λ^′-connected, if λ^′(G) exists.In 1988, Esfahanian and Hakimi [A.H. Esfahanian, S.L. Hakimi, On computing a conditional edge-connectivity of a graph, Inform. Process. Lett. 27 (1988), 195-199] have shown that each connected graph G of order n?4, except a star, is λ^′-connected and satisfies λ^′(G)?ξ(G), where ξ(G) is the minimum edge-degree of G.If D is a strongly connected digraph, then we call in this paper an arc set S a restricted arc-cut of D if D−S has a non-trivial strong component D₁ such that D−V(D₁) contains an arc. The restricted arc-connectivity λ^′(D) is the minimum cardinality over all restricted arc-cuts S.We observe that the recognition problem, whether λ^′(D) exists for a strongly connected digraph D is solvable in polynomial time. Furthermore, we present some analogous results to the above mentioned theorem of Esfahanian and Hakimi for digraphs, and we show that this theorem follows easily from one of our results.     

The complexity of changing colourings with bounded maximum degree

Let G be a graph, x,y∈V(G), and ?:V(G)→[k] a k-colouring of G such that ?(x)=?(y). If then the following question is NP-complete: Does there exist a k-colouring ?^′ of G such that ?^′(x)≠?^′(y)? Conversely, if then the problem is polynomial time.     

List edge and list total colorings of planar graphs without short cycles

Let G be a planar graph with maximum degree Δ(G). We use and to denote the list edge chromatic number and list total chromatic number of G, respectively. In this paper, it is proved that and if Δ(G)?6 and G has neither C₄ nor C₆, or Δ(G)?7 and G has neither C₅ nor C₆, where Ck is a cycle of length k.     

On the oriented chromatic number of Halin graphs

An oriented k-coloring of an oriented graph G is a mapping such that (i) if xy∈E(G) then c(x)≠c(y) and (ii) if xy,zt∈E(G) then c(x)=c(t)⇒c(y)≠c(z). The oriented chromatic number of an oriented graph G is defined as the smallest k such that G admits an oriented k-coloring. We prove in this paper that every Halin graph has oriented chromatic number at most 9, improving a previous bound proposed by Vignal.     

Edge-choosability of planar graphs without non-induced 5-cycles

A graph G is edge-L-colorable, if for a given edge assignment , there exits a proper edge-coloring ? of G such that ?(e)∈L(e) for all e∈E(G). If G is edge-L-colorable for every edge assignment L with |L(e)|?k for e∈E(G), then G is said to be edge-k-choosable. In this paper, we prove that if G is a planar graph without non-induced 5-cycles, then G is edge-k-choosable, where k=max{7,Δ(G)+1}.     

Ranking numbers of graphs

Given a graph G, a vertex ranking (or simply, ranking) of G is a mapping f from V(G) to the set of all positive integers, such that for any path between two distinct vertices u and v with f(u)=f(v), there is a vertex w in the path with f(w)>f(u). If f is a ranking of G, the ranking number of G under f, denoted γf(G), is defined by , and the ranking number of G, denoted γ(G), is defined by . The vertex ranking problem is to determine the ranking number γ(G) of a given graph G. This problem is a natural model for the manufacturing scheduling problem. We study the ranking numbers of graphs in this paper. We consider the relation between the ranking numbers and the minimal cut sets, and the relation between the ranking numbers and the independent sets. From this, we obtain the ranking numbers of the powers of paths and the powers of cycles, the Cartesian product of P₂ with Pn or Cn, and the caterpilars. And we also find the vertex ranking numbers of the composition of two graphs in this paper.     

Spectral radius minimization for optimal average consensus and output feedback stabilization

In this paper, we consider two problems which can be posed as spectral radius minimization problems. Firstly, we consider the fastest average agreement problem on multi-agent networks adopting a linear information exchange protocol. Mathematically, this problem can be cast as finding an optimal such that x(k+1)=Wx(k), , and W∈S(E). Here, is the value possessed by the agents at the kth time step, is an all-one vector and S(E) is the set of real matrices in with zeros at the same positions specified by a network graph G(V,E), where V is the set of agents and E is the set of communication links between agents. The optimal W is such that the spectral radius is minimized. To this end, we consider two numerical solution schemes: one using the qth-order spectral norm (2-norm) minimization (q-SNM) and the other gradient sampling (GS), inspired by the methods proposed in [Burke, J., Lewis, A., & Overton, M. (2002). Two numerical methods for optimizing matrix stability. Linear Algebra and its Applications, 351-352, 117-145; Xiao, L., & Boyd, S. (2004). Fast linear iterations for distributed averaging. Systems & Control Letters, 53(1), 65-78]. In this context, we theoretically show that when E is symmetric, i.e. no information flow from the ith to the jth agent implies no information flow from the jth to the ith agent, the solution from the 1-SNM method can be chosen to be symmetric and is a local minimum of the function . Numerically, we show that the q-SNM method performs much better than the GS method when E is not symmetric. Secondly, we consider the famous static output feedback stabilization problem, which is considered to be a hard problem (some think NP-hard): for a given linear system (A,B,C), find a stabilizing control gain K such that all the real parts of the eigenvalues of A+BKC are strictly negative. In spite of its computational complexity, we show numerically that q-SNM successfully yields stabilizing controllers for several benchmark problems with little effort.     

Super-connected and super-arc-connected Cartesian product of digraphs

We study the super-connected, hyper-connected and super-arc-connected Cartesian product of digraphs. The following two main results will be obtained:

(i)

If δ⁺(Di)=δ⁻(Di)=δ(Di)=κ(Di) for i=1,2, then D₁×D₂ is super-κ if and only if ,

(ii)

If δ⁺(Di)=δ⁻(Di)=δ(Di)=λ(Di) for i=1,2, then D₁×D₂ is super-λ if and only if ,

where λ(D)=δ(D)=1, denotes the complete digraph of order n and n?2.     

Triggering cascades on undirected connected graphs

Consider the following cascading process on an undirected connected graph G(V,E). A set S of vertices, called the seeds, are active initially. Thereafter, an inactive vertex is activated when at least a ρ fraction of its neighbors is active, where ρ∈(0,1]. The cascading process proceeds asynchronously until no more vertices can be activated. This paper proves the existence of at most seeds that can activate all vertices at the end.     

An approximation algorithm dependent on edge-coloring number for minimum maximal matching problem

We consider the minimum maximal matching problem, which is NP-hard (Yannakakis and Gavril (1980) [18]). Given an unweighted simple graph G=(V,E), the problem seeks to find a maximal matching of minimum cardinality. It was unknown whether there exists a non-trivial approximation algorithm whose approximation ratio is less than 2 for any simple graph. Recently, Z. Gotthilf et al. (2008) [5] presented a -approximation algorithm, where c is an arbitrary constant.In this paper, we present a -approximation algorithm based on an LP relaxation, where χ^′(G) is the edge-coloring number of G. Our algorithm is the first non-trivial approximation algorithm whose approximation ratio is independent of |V|. Moreover, it is known that the minimum maximal matching problem is equivalent to the edge dominating set problem. Therefore, the edge dominating set problem is also -approximable. From edge-coloring theory, the approximation ratio of our algorithm is , where Δ(G) represents the maximum degree of G. In our algorithm, an LP formulation for the edge dominating set problem is used. Fujito and Nagamochi (2002) [4] showed the integrality gap of the LP formulation for bipartite graphs is at least . Moreover, χ^′(G) is Δ(G) for bipartite graphs. Thus, as far as an approximation algorithm for the minimum maximal matching problem uses the LP formulation, we believe our result is the best possible.     

Vertex fault tolerance of optimal-κ graphs and super-κ graphs

A connected graph G is optimal-κ if κ(G)=δ(G). It is super-κ if every minimum vertex cut isolates a vertex. An optimal-κ graph G is m-optimal-κ if for any vertex set S⊆V(G) with |S|?m, G−S is still optimal-κ. We define the vertex fault tolerance with respect to optimal-κ, denoted by Oκ(G), as the maximum integer m such that G is m-optimal-κ. The concept of vertex fault tolerance with respect to super-κ, denoted by Sκ(G), is defined in a similar way. In this paper, we show that min{κ₁(G)−δ(G),δ(G)−1}?Oκ(G)?δ(G)−1 and min{κ₁(G)−δ(G)−1,δ(G)−1}?Sκ(G)?δ(G)−1, where κ₁(G) is the 1-extra connectivity of G. Furthermore, when the graph is triangle free, more refined lower bound can be derived for Oκ(G).     

Signed and minus clique-transversal functions on graphs

A minus (respectively, signed) clique-transversal function of a graph G=(V,E) is a function (respectively, {−1,1}) such that _∑u∈Cf(u)?1 for every maximal clique C of G. The weight of a minus (respectively, signed) clique-transversal function of G is f(V)=_∑v∈Vf(v). The minus (respectively, signed) clique-transversal problem is to find a minus (respectively, signed) clique-transversal function of G of minimum weight. In this paper, we present a unified approach to these two problems on strongly chordal graphs. Notice that trees, block graphs, interval graphs, and directed path graphs are subclasses of strongly chordal graphs. We also prove that the signed clique-transversal problem is NP-complete for chordal graphs and planar graphs.