Search

A neighbor-sum-distinguishing W -edge-weighting of a graph G = (V , E) is an assignment ω of weights from a set of integers W to the set of edges E of G such that for every pair of adjacent vertices, the incident sums induced by the edge-weighting are different, where the incident sum of a vertex v induced by the edge-weighting ω is σ (v) = ∑ u ∈ N (v) ω (u v) , where N (v) is the set of neighbors of v in G. Whereas, a neighbor-sum- 2 -distinguishing W-edge-weighting of G is a neighbor-sum-distinguishing W -edge-weighting such that the incident sums of every pair of adjacent vertices differ by at least 2. A recently proposed conjecture about neighbor-sum-2-distinguishing { 1 , 3 , 5 } -edge-weighting states that any graph with no component isomorphic to K 2 admits a neighbor-sum-2-distinguishing { 1 , 3 , 5 } -edge-weighting. In this paper, we prove that deciding whether there exists a neighbor-sum-2-distinguishing { 1 , 3 } -edge-weighting is NP-complete for bipartite graphs. We present an algorithm that computes a neighbor-sum-2-distinguishing { 1 , 3 } -edge-weighting of the central graph of any graph in polynomial time and thus proves the above conjecture for the central graph of any graph. Further, we establish that if any pair of graphs G and H admit neighbor-sum-2-distinguishing edge-weightings, then so does their Cartesian product, G □ H. We study another aspect of neighbor-sum-2-distinguishing edge-weighting of a graph G , namely, the minimum number of incident sums used by a neighbor-sum-2-distinguishing { 1 , 3 } -edge-weighting, which is denoted by γ Σ > 1 , { 1 , 3 } (G). We prove that the problems of deciding whether there exists a neighbor-sum-2-distinguishing { 1 , 3 } -edge-weighting of G from a given set of sums, and deciding whether γ Σ > 1 , { 1 , 3 } (G) ≤ k are NP-complete for bipartite graphs. On the positive side, we provide both upper and lower bounds on γ Σ > 1 , { 1 , 3 } (C (G)) for central graphs of bipartite graphs and split graphs. We also propose an algorithm that computes the optimal neighbor-sum-2-distinguishing { 1 , 3 } -edge-weighting of the central graphs of cycles and paths in polynomial time. [ABSTRACT FROM AUTHOR]

A subset M ⊆ E of edges of a graph G = (V , E) is called a matching if no two edges of M share a common vertex. An edge e ∈ E is said to dominate itself and all other edges adjacent to it. A matching M in a graph G = (V , E) is called a dominating induced matching (d.i.m.) if every edge of G is dominated by edges of M exactly once. The dominating induced matching decide (DIM-Decide) problem asks whether a graph G contains a dominating induced matching. The dominating induced matching (DIM) problem asks to compute a dominating induced matching (d.i.m.) in a graph G that admits a dominating induced matching. The DIM-Decide problem is known to be NP-complete for general graphs as well as for bipartite graphs. In this paper, we strengthen the NP-completeness result of the DIM-Decide problem by showing that this problem remains NP-complete for perfect elimination bipartite graphs, a proper subclass of bipartite graphs. On the positive side, we characterize the class of star-convex bipartite graphs admitting a d.i.m. This characterization leads to a linear time algorithm to test whether a star-convex bipartite graph admits a d.i.m. and, if so, constructs a d.i.m. in such a star-convex bipartite graph in linear time. We also propose polynomial time algorithms to construct a d.i.m. in long- k -star-convex bipartite graphs as well as in circular-convex bipartite graphs if the input graph admits a d.i.m. [ABSTRACT FROM AUTHOR]

• We prove that Decide-UR Matching problem is NP-complete for chordal bipartite graphs and star-convex bipartite graphs. • We prove that Decide-UR Matching problem is NP-complete for chordal graphs and doubly chordal graphs. • We prove that a minimum cardinality maximal uniquely restricted matching can be computed in polynomial time for bipartite distance-hereditary graphs. • We prove that a minimum cardinality maximal uniquely restricted matching can be computed in linear time for bipartite permutation graphs, proper interval graphs, and threshold graphs. • We prove that the problem is APX-complete for bounded degree graphs. A subset M ⊆ E of edges of a graph G = (V , E) is called a matching if no two edges of M share a common vertex. A matching M in a graph G is called a uniquely restricted matching if, G [ V (M) ] , the subgraph of G induced by the set of M -saturated vertices of G contains exactly one perfect matching. A uniquely restricted matching M is maximal if M is not properly contained in any uniquely restricted matching of G. Given a graph G , the Min-Max-UR Matching problem asks to find a maximal uniquely restricted matching in G of minimum cardinality and Decide-Min-Max-UR Matching problem, the decision version of this problem takes a graph G and an integer k and asks whether G admits a maximal uniquely restricted matching of cardinality at most k. It is known that the Decide-Min-Max-UR Matching problem is NP-complete. In this paper, we strengthen this result by proving that the Decide-Min-Max-UR Matching problem remains NP -complete for chordal bipartite graphs, star-convex bipartite graphs, chordal graphs, and doubly chordal graphs. On the positive side, we prove that the Min-Max-UR Matching problem is polynomial time solvable for bipartite distance-hereditary graphs and linear time solvable for bipartite permutation graphs, proper interval graphs, and threshold graphs. Finally, we prove that the Min-Max-UR Matching problem is APX -complete for graphs with maximum degree 4. [ABSTRACT FROM AUTHOR]

A total dominating set of a graph G = (V , E) is a subset D of V such that every vertex in V is adjacent to at least one vertex of the set D. A total dominating set D of G is a differentiating-total dominating set of G if for every pair of distinct vertices u , v ∈ V , N G [ u ] ∩ D ≠ N G [ v ] ∩ D. Given a graph G , Minimum Differentiating-Total Domination is to find a differentiating-total dominating set of minimum cardinality of G and Decide Differentiating-Total Domination is the decision version of Minimum Differentiating-Total Domination. In this paper, we initiate the algorithmic study of Minimum Differentiating-Total Domination. We show that Decide Differentiating-Total Domination is NP -complete for chordal graphs, chordal bipartite graphs, star-convex bipartite graphs, and planar graphs. On the positive side, we propose an O (log ⁡ Δ) factor approximation algorithm for Minimum Differentiating-Total Domination for any graph G with maximum degree Δ. We match the above upper bound by showing that for general graphs as well as for bipartite graphs Minimum Differentiating-Total Domination cannot be approximated within a factor of (1 2 − ε) ln ⁡ | V | for any ε > 0 unless P = NP. Finally, we show that Minimum Differentiating-Total Domination is APX -complete for bounded degree bipartite graphs. [ABSTRACT FROM AUTHOR]

A subset D ⊆ V of a graph G = (V , E) is called a global total k -dominating set of G if D is a total k -dominating set of both G and the complement G ‾ of G. The Minimum Global Total k -Domination problem is to find a global total k -dominating set of minimum cardinality of the input graph G and Decide Global Total k -Domination problem is the decision version of Minimum Global Total k -Domination problem. The Decide Global Total k -Domination problem is known to be NP -complete for general graphs as well as for bipartite graphs. In this paper, we strengthen the NP -completeness result of Decide Global Total k -Domination problem by showing that this problem remains NP -complete for perfect elimination bipartite graphs, star-convex bipartite graphs and doubly chordal graphs. On the positive side, we give a polynomial time algorithm for the Minimum Global Total k -Domination problem for chordal bipartite graphs, which is a subclass of bipartite graphs. We propose a 2 (1 + ln ⁡ | V |) -approximation algorithm for the Minimum Global Total k -Domination problem for any graph. We show that Minimum Global Total k -Domination problem cannot be approximated within (1 − ϵ) ln ⁡ | V | for any ϵ > 0 unless P = NP for any integer k ≥ 1. We further show that for bipartite graphs, Minimum Global Total k -Domination problem cannot be approximated within (1 6 − ϵ) ln ⁡ | V | for any ϵ > 0 unless P = NP for any k ≥ 1. Finally, we show that the Minimum Global Total k -Domination problem is APX -complete for bounded degree bipartite graphs for any fixed integer k ≥ 1. [ABSTRACT FROM AUTHOR]

This paper makes progress towards settling the long-standing conjecture that the total chromatic number χ ″ of the complete p -partite graph K = K ( r 1 , … , r p ) is Δ ( K ) + 1 if and only if K ≠ K r , r and if K has an even number of vertices then Σ v ∈ V ( K ) ( Δ ( K ) − d K ( v ) ) is at least the number of parts of odd size. Graphs of even order that are fairly close to being regular are the ones for which χ ″ ( K ) remains in doubt. In this paper we show that K is of Type 1 if | V ( K ) | is even and r 2 < r 3 (with parts arranged in non-decreasing order of size), thereby improving on the result of Dong and Yap published in 2000. Furthermore, it is shown using this result together with the novel approach of graph amalgamations that all complete multipartite graphs of the form K ( r , r , … , r , r + 1 ) are of Type 1. [ABSTRACT FROM AUTHOR]

The authors propose three variants of distributed and stateless forwarding strategies for wireless sensor networks, namely greedy minimum energy consumption forwarding protocol (GMFP), lifetime maximising GMFP (LM-GMFP) and variance minimising GMFP (VAR-GMFP), which aim at maximising the network lifetime while achieving a high forwarding success rate. GMFP selects a forwarding node that minimises per-packet energy consumption while maximising the forwarding progress. LM-GMFP extends the GMFP algorithm by also taking into account the remaining energy at the prospective one-hop forwarding nodes. In VAR-GMFP, on the other hand, the packet is forwarded to the next node that ensures a locally high mean and low variance of nodal remaining energy. Through simple probabilistic analysis the authors prove the intuition behind the optimum forwarding node selection for network lifetime maximisation. They then model the lifetime maximisation of a sensor network as an optimisation problem and compare the practical protocol-dependent network lifetime with the theoretical upper bound. Through extensive simulations the author demonstrate that the proposed protocols outperform the existing energy-aware protocols in terms of network lifetime and end-to-end delay. [ABSTRACT FROM AUTHOR]

Abstract: An -labeling of a graph is an assignment of nonnegative integers, called colors, to the vertices of such that the difference between the colors assigned to any two adjacent vertices is at least two and the difference between the colors assigned to any two vertices which are at distance two apart is at least one. The span of an -labeling is the maximum color number that has been assigned to a vertex of by . The -labeling number of a graph , denoted as , is the least integer such that has an -labeling of span . In this paper, we propose a linear time algorithm to -label a chain graph optimally. We present constant approximation -labeling algorithms for various subclasses of chordal bipartite graphs. We show that for a chordal bipartite graph , where is the maximum degree of . However, we show that there are perfect elimination bipartite graphs having . Finally, we prove that computing of a perfect elimination bipartite graph is NP-hard. [Copyright &y& Elsevier]

Abstract: A spanning tree of a graph is said to be a tree -spanner if the distance between any two vertices in is at most times their distance in . A graph that has a tree -spanner is called a tree -spanner admissible graph. The problem of deciding whether a graph is tree -spanner admissible is NP-complete for any fixed and is linearly solvable for . The case still remains open. A chordal graph is called a 2-sep chordal graph if all of its minimal vertex separators for every pair of non-adjacent vertices and are of size two. It is known that not all 2-sep chordal graphs admit tree 3-spanners. This paper presents a structural characterization and a linear time recognition algorithm of tree 3-spanner admissible 2-sep chordal graphs. Finally, a linear time algorithm to construct a tree 3-spanner of a tree 3-spanner admissible 2-sep chordal graph is proposed. [ABSTRACT FROM AUTHOR]

Abstract: A spanning tree of a graph is called a tree -spanner, if the distance between any two vertices in is at most -times their distance in . A graph that has a tree -spanner is called a tree -spanner admissible graph. The problem of deciding whether a graph is tree -spanner admissible is NP-complete for any fixed , and is linearly solvable for and . The case still remains open. A directed path graph is called a 2-sep directed path graph if all of its minimal vertex separator for every pair of non-adjacent vertices and are of size two. Le and Le [H.-O. Le, V.B. Le, Optimal tree 3-spanners in directed path graphs, Networks 34 (2) (1999) 81–87] showed that directed path graphs admit tree 3-spanners. However, this result has been shown to be incorrect by Panda and Das [B.S. Panda, Anita Das, On tree 3-spanners in directed path graphs, Networks 50 (3) (2007) 203–210]. In fact, this paper observes that even the class of 2-sep directed path graphs, which is a proper subclass of directed path graphs, need not admit tree 3-spanners in general. It, then, presents a structural characterization of tree 3-spanner admissible 2-sep directed path graphs. Based on this characterization, a linear time recognition algorithm for tree 3-spanner admissible 2-sep directed path graphs is presented. Finally, a linear time algorithm to construct a tree 3-spanner of a tree 3-spanner admissible 2-sep directed path graph is proposed. [Copyright &y& Elsevier]