A linear-time algorithm for weighted paired-domination on block graphs

Journal of Combinatorial Optimization - In a graph $$G = (V,E)$$ , a set $$S\subseteq V(G)$$ is said to be a dominating set of G if every vertex not in S is adjacent to a vertex in S. Let G[S]...     

The upper bounds on the Steiner k-Wiener index in terms of minimum and maximum degrees

Journal of Combinatorial Optimization - For $$k \in {\mathbb {N}},$$ Ali et al. (Discrete Appl Math 160:1845-1850, 2012) introduce the Steiner k-Wiener index $$SW_{k}(G)=\sum _{S\in V(G)} d(S),$$...     

Paired domination versus domination and packing number in graphs

Journal of Combinatorial Optimization - Given a graph $$G=(V(G), E(G))$$ , the size of a minimum dominating set, minimum paired dominating set, and a minimum total dominating set of a graph G are...     

On the adjacent vertex-distinguishing total chromatic numbers of the graphs with Δ (G) = 3

Let be a simple graph and T(G) be the set of vertices and edges of G. Let C be a k-color set. A (proper) total k-coloring f of G is a function such that no adjacent or incident elements of T(G) receive the same color. For any , denote . The total k-coloring f of G is called the adjacent vertex-distinguishing if for any edge . And the smallest number of colors is called the adjacent vertex-distinguishing total chromatic number of G. In this paper, we prove that for all connected graphs with maximum degree three. This is a step towards a conjecture on the adjacent vertex-distinguishing total coloring. MSC: 05C15     

On the relation between Wiener index and eccentricity of a graph

Journal of Combinatorial Optimization - The relation between the Wiener index W(G) and the eccentricity $$\varepsilon (G)$$ of a graph G is studied. Lower and upper bounds on W(G) in terms of...     

The signed edge-domatic number of nearly cubic graphs

Journal of Combinatorial Optimization - A signed edge-domination of graph G is a function $$f:\ E(G)\rightarrow \{+1,-1\}$$ such that $$\sum _{e'\in N_{G}[e]}{f(e')}\ge 1$$ for each $$e\in...     

On metric dimension of plane graphs with $$\frac{m}{2}$$ number of 10 sided faces

Journal of Combinatorial Optimization - Let $$\Gamma =\Gamma (V, E)$$ be a simple (multiple edges and loops are not considered), connected (every pair of distinct vertices are joined by a path),...     

Approximation hardness of edge dominating set problems

We provide the first interesting explicit lower bounds on efficient approximability for two closely related optimization problems in graphs, MINIMUM EDGE DOMINATING SET and MINIMUM MAXIMAL MATCHING. We show that it is NP-hard to approximate the solution of both problems to within any constant factor smaller than . The result extends with negligible loss to bounded degree graphs and to everywhere dense graphs. An extended abstract of this paper was accepted at the 14th Annual International Symposium on Algorithms and Computation, ISAAC 2003.     

A sifting-edges algorithm for accelerating the computation of absolute 1-center in graphs

Journal of Combinatorial Optimization - Let $$G = (V, E, w)$$ be an undirected connected edge-weighted graph, where V is the n-vertices set, E is the m-edges set, and $$w: E \rightarrow \mathbb...     

Improved formulations and branch-and-cut algorithms for the angular constrained minimum spanning tree problem

Journal of Combinatorial Optimization - The Angular Constrained Minimum Spanning Tree Problem ( $$\alpha $$ -MSTP) is defined in terms of a complete undirected graph $$G=(V,E)$$ and an angle...     

Atoms of cyclic edge connectivity in regular graphs

A cyclic edge-cut of a connected graph \(G\) is an edge set, the removal of which separates two cycles. If \(G\) has a cyclic edge-cut, then it is called cyclically separable. For a cyclically separable graph \(G\), the cyclic edge connectivity of a graph \(G\), denoted by \(\lambda _c(G)\), is the minimum cardinality over all cyclic edge cuts. Let \(X\) be a non-empty proper subset of \(V(G)\). If \([X,\overline{X}]=\{xy\in E(G)\ |\ x\in X, y\in \overline{X}\}\) is a minimum cyclic edge cut of \(G\), then \(X\) is called a \(\lambda _c\) -fragment of \(G\). A \(\lambda _c\)-fragment with minimum cardinality is called a \(\lambda _c\) -atom. Let \(G\) be a \(k (k\ge 3)\)-regular cyclically separable graph with \(\lambda _c(G)<g(k-2)\), where \(g\) is the girth of \(G\). A combination of the results of Nedela and Skoviera (Math Slovaca 45:481–499, 1995) and Xu and Liu (Australas J Combin 30:41–49, 2004) gives that if \(k\ne 5\) then any two distinct \(\lambda _c\)-atoms of \(G\) are disjoint. The remaining case of \(k=5\) is considered in this paper, and a new proof for Nedela and ?koviera’s result is also given. As a result, we obtain the following result. If \(X\) and \(X'\) are two distinct \(\lambda _c\)-atoms of \(G\) such that \(X\cap X'\ne \emptyset \), then \((k,g)=(5,3)\) and \(G[X]\cong K_4\). As corollaries, several previous results are easily obtained.     

Total edge irregularity strength of accordion graphs

An edge irregular total k-labeling \(\varphi : V\cup E \rightarrow \{ 1,2, \dots , k \}\) of a graph \(G=(V,E)\) is a labeling of vertices and edges of G in such a way that for any different edges xy and \(x'y'\) their weights \(\varphi (x)+ \varphi (xy) + \varphi (y)\) and \(\varphi (x')+ \varphi (x'y') + \varphi (y')\) are distinct. The total edge irregularity strength, tes(G), is defined as the minimum k for which G has an edge irregular total k-labeling. We have determined the exact value of the total edge irregularity strength of accordion graphs.     

Incremental optimization of independent sets under the reconfiguration framework

Journal of Combinatorial Optimization - Suppose that we are given an independent set $$I_0$$ of a graph G, and an integer $$l\ge 0$$ . Then, we are asked to find an independent set of G having the...     

Distance constrained vehicle routing problem to minimize the total cost: algorithms and complexity

Journal of Combinatorial Optimization - Given $$\lambda &gt;0$$ , an undirected complete graph $$G=(V,E)$$ with nonnegative edge-weight function obeying the triangle inequality and a depot...     

Results on vertex-edge and independent vertex-edge domination

Journal of Combinatorial Optimization - Given a graph $$G = (V,E)$$ , a vertex $$u \in V$$ ve-dominates all edges incident to any vertex of $$N_G[u]$$ . A set $$S \subseteq V$$ is a ve-dominating...     

Sharp upper bound of injective coloring of planar graphs with girth at least 5

Journal of Combinatorial Optimization - An injective k-coloring of a graph G is a k-coloring c (not necessarily proper) such that $$c(u)\ne c(v)$$ whenever u, v has a common neighbor in G. The...     

Graphs with large paired-domination number

In this paper, we continue the study of paired-domination in graphs introduced by Haynes and Slater (1998) Networks 32: 199–206. A paired-dominating set of a graph G with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number of G, denoted by , is the minimum cardinality of a paired-dominating set of G. Let G be a connected graph of order n with minimum degree at least two. Haynes and Slater (1998) Networks 32: 199–206, showed that if n ≥ 6, then . In this paper, we show that there are exactly ten graphs that achieve equality in this bound. For n ≥ 14, we show that and we characterize the (infinite family of) graphs that achieve equality in this bound.Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal.     

Neighbor-sum-distinguishing edge choosability of subcubic graphs

A graph G is said to be neighbor-sum-distinguishing edge k-choose if, for every list L of colors such that L(e) is a set of k positive real numbers for every edge e, there exists a proper edge coloring which assigns to each edge a color from its list so that for each pair of adjacent vertices u and v the sum of colors taken on the edges incident to u is different from the sum of colors taken on the edges incident to v. Let \(\mathrm{ch}^{\prime }_{\sum ^p}(G)\) denote the smallest integer k such that G is neighbor-sum-distinguishing edge k-choose. In this paper, we prove that if G is a subcubic graph with the maximum average degree mad(G), then (1) \(\mathrm{ch}^{\prime }_{\sum ^p}(G)\le 7\); (2) \(\mathrm{ch}^{\prime }_{\sum ^p}(G)\le 6\) if \(\hbox {mad}(G)<\frac{36}{13}\); (3) \(\mathrm{ch}^{\prime }_{\sum ^p}(G)\le 5\) if \(\hbox {mad}(G)<\frac{5}{2}\).     

Partial degree bounded edge pacing problem for graphs and $$$$-uniform hypergraphs

Given a graph \(G=(V,E)\) and a non-negative integer \(c_u\) for each \(u\in V\), partial degree bounded edge packing problem is to find a subgraph \(G^{\prime }=(V,E^{\prime })\) with maximum \(|E^{\prime }|\) such that for each edge \((u,v)\in E^{\prime }\), either \(deg_{G^{\prime }}(u)\le c_u\) or \(deg_{G^{\prime }}(v)\le c_v\). The problem has been shown to be NP-hard even for uniform degree constraint (i.e., all \(c_u\) being equal). In this work we study the general degree constraint case (arbitrary degree constraint for each vertex) and present two combinatorial approximation algorithms with approximation factors \(4\) and \(2\). Then we give a \(\log _2 n\) approximation algorithm for edge-weighted version of the problem and an efficient exact algorithm for edge-weighted trees with time complexity \(O(n\log n)\). We also consider a generalization of this problem to \(k\)-uniform hypergraphs and present a constant factor approximation algorithm based on linear programming using Lagrangian relaxation.     

Approximation algorithms for the maximally balanced connected graph tripartition problem

Journal of Combinatorial Optimization - Given a vertex-weighted connected graph $$G = (V, E, w(\cdot ))$$ , the maximally balanced connected graph k-partition (k-BGP) seeks to partition the vertex...