On the efficiency index of a graph

A graph \(G\) has an efficient dominating set \(D \subseteq V(G)\) if \(D\) dominates every vertex exactly once. In this paper we introduce the study of the family \({S_k}\) of graphs for which every \(G-S\) is efficiently dominatable for \(0 \le |S|\le k\). Assuming that \(G\) is efficiently dominatable, the efficiency index is the largest value k for which \(G\) is in \(S_k\). A graph \(G\) will be called super-efficient if every induced subgraph is efficiently dominatable. We give some characterizations for trees, grids, cylinders and torii to be super-efficient.     

On the most imbalanced orientation of a graph

We study the problem of orienting the edges of a graph such that the minimum over all the vertices of the absolute difference between the outdegree and the indegree of a vertex is maximized. We call this minimum the imbalance of the orientation, i.e. the higher it gets, the more imbalanced the orientation is. The studied problem is denoted by \({{\mathrm{\textsc {MaxIm}}}}\). We first characterize graphs for which the optimal objective value of \({{\mathrm{\textsc {MaxIm}}}}\) is zero. Next we show that \({{\mathrm{\textsc {MaxIm}}}}\) is generally NP-hard and cannot be approximated within a ratio of \(\frac{1}{2}+\varepsilon \) for any constant \(\varepsilon >0\) in polynomial time unless \(\texttt {P}=\texttt {NP}\) even if the minimum degree of the graph \(\delta \) equals 2. Then we describe a polynomial-time approximation algorithm whose ratio is almost equal to \(\frac{1}{2}\). An exact polynomial-time algorithm is also derived for cacti. Finally, two mixed integer linear programming formulations are presented. Several valid inequalities are exhibited with the related separation algorithms. The performance of the strengthened formulations is assessed through several numerical experiments.     

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

On identifying codes in the Cartesian product of a path and a complete graph

Identifying codes in the Cartesian product of a complete graph and a path are considered. After proving a set of sufficient conditions for a set in such a graph to be an identifying code, we then construct minimum identifying codes when the complete graph is of order three or at least five, and when the path is of order at least three.     

On edge orienting methods for graph coloring

We consider the problem of orienting the edges of a graph so that the length of a longest path in the resulting digraph is minimum. As shown by Gallai, Roy and Vitaver, this edge orienting problem is equivalent to finding the chromatic number of a graph. We study various properties of edge orienting methods in the context of local search for graph coloring. We then exploit these properties to derive four tabu search algorithms, each based on a different neighborhood. We compare these algorithms numerically to determine which are the most promising and to give potential research directions.     

On the generalized constrained longest common subsequence problems

We investigate four variants of the longest common subsequence problem. Given two sequences X, Y and a constrained pattern P of lengths m, n, and ρ, respectively, the generalized constrained longest common subsequence (GC-LCS) problems are to find a longest common subsequence of X and Y including (or excluding) P as a subsequence (or substring). We propose new dynamic programming algorithms for solving the GC-LCS problems in O(mn ρ) time. We also consider the case where the number of constrained patterns is arbitrary.     

On the generalized multiway cut in trees problem

Given a tree $T = (V, E)$ with $n$ vertices and a collection of terminal sets $D = \{S_1, S_2, \ldots , S_c\}$ , where each $S_i$ is a subset of $V$ and $c$ is a constant, the generalized multiway cut in trees problem (GMWC(T)) asks to find a minimum size edge subset $E^{\prime } \subseteq E$ such that its removal from the tree separates all terminals in $S_i$ from each other for each terminal set $S_i$ . The GMWC(T) problem is a natural generalization of the classical multiway cut in trees problem, and has an implicit relation to the Densest $k$ -Subgraph problem. In this paper, we show that the GMWC(T) problem is fixed-parameter tractable by giving an $O(n^2 + 2^k)$ time algorithm, where $k$ is the size of an optimal solution, and the GMWC(T) problem is polynomial time solvable when the problem is restricted in paths.We also discuss some heuristics for the GMWC(T) problem     

On the power domination number of the generalized Petersen graphs

The problem of monitoring an electric power system by placing as few measurement devices in the system as possible is closely related to the well-known domination problem in graphs. Following a set of rules for power system monitoring, a set S of vertices is defined to be a power dominating set of a graph if every vertex and every edge in the system is monitored by the set S. The minimum cardinality of a power dominating set of G is the power domination number γ _p (G). In this paper, we investigate the power domination number for the generalized Petersen graphs, presenting both upper bounds for such graphs and exact results for a subfamily of generalized Petersen graphs.     

Spanning tree of a multiple graph

Journal of Combinatorial Optimization - We study undirected multiple graphs of any natural multiplicity $$k>1$$ . There are edges of three types: ordinary edges, multiple edges and...     

The optimum traversal of a graph

For a given graph (network) having costs [c_ij] associated with its links, the present paper examines the problem of finding a cycle which traverses every link of the graph at least once, and which incurs the minimum cost of traversal. This problem (called thegraph traversal problem, or theChinese postman problem [9]) can be formulated in ways analogous to those used for the well-known travelling salesman problem, and using this apparent similarity, Bellman and Cooke [1] have produced a dynamic programming formulation. This method of solution of the graph traversal problem requires computational times which increase exponentially with the number of links in the graph. Approximately the same rate of increase of computational effort with problem size would result by any other method adapting a travelling salesman algorithm to the present problem.This paper describes an efficient algorithm for the optimal solution of the graph traversal problem based on the matching method of Edmonds [5, 6]. The computational time requirements of this algorithm increase as a low order (2 or 3) power of the number of links in the graph. Computational results are given for graphs of up to 50 vertices and 125 links.The paper then discusses a generalised version of the graph traversal problem, where not one but a number of cycles are required to traverse the graph. In this case each link has (in addition to its cost) a quantity q_ij associated with it, and the sum of the quantities of the links in any one cycle must be less than a given amount representing the cycle capacity. A heuristic algorithm for the solution of this problem is given. The algorithm is based on the optimal algorithm for the single-cycle graph traversal problem and is shown to produce near-optimal results.There is a large number of possible applications where graph traversal problems arise. These applications include: the spraying of roads with salt-grit to prevent ice formation, the inspection of electric power lines, gas, or oil pipelines for faults, the delivery of letter post, etc.     

Faster algorithm to find anti-risk path between two nodes of an undirected graph

For a weighted 2-edge connected graph G=(V,E), we are to find a “minimum risk path” from source s to destination t. This is a shortest s?t path under the assumption that at most one edge on the path may be blocked. The fact that the edge is blocked is known only when we reach a site adjacent to the blocked edge. If n and m are the number of nodes and edges of G, then we show that this problem can be solved in O(n ²) time using only simple data structures. This is an improvement over the previous O(mn+n ²logn) time algorithm. Moreover, with use of more complicated data structures like Fibonacci Heaps and transmuters the time can be further reduced to O(m+nlogn).     

The capture time of a planar graph

This paper examines the capture time of a planar graph in a variant of the pursuit-evasion games, called cops and robbers game. Since any planar graph is 3-cop-win, we study the capture time of a planar graph G of n vertices using three cops, which is denoted by \(capt_3(G)\). We present a new capture strategy and show that \(capt_3(G) \le 2n\). This is the first result on \(capt_3(G)\).     

Roman game domination number of a graph

The Roman game domination number of an undirected graph G is defined by the following game. Players \(\mathcal {A}\) and \(\mathcal {D}\) orient the edges of the graph G alternately, with \(\mathcal {D}\) playing first, until all edges are oriented. Player \(\mathcal {D}\) (frequently called Dominator) tries to minimize the Roman domination number of the resulting digraph, while player \(\mathcal {A}\) (Avoider) tries to maximize it. This game gives a unique number depending only on G, if we suppose that both \(\mathcal {A}\) and \(\mathcal {D}\) play according to their optimal strategies. This number is called the Roman game domination number of G and is denoted by \(\gamma _{Rg}(G)\). In this paper we initiate the study of the Roman game domination number of a graph and we establish some bounds on \(\gamma _{Rg}(G)\). We also determine the Roman game domination number for some classes of graphs.     

Enumerating the edge-colourings and total colourings of a regular graph

In this paper, we are interested in computing the number of edge colourings and total colourings of a connected graph. We prove that the maximum number of k-edge-colourings of a connected k-regular graph on n vertices is k?((k?1)!) ^n/2. Our proof is constructive and leads to a branching algorithm enumerating all the k-edge-colourings of a connected k-regular graph in time O ^?(((k?1)!) ^n/2) and polynomial space. In particular, we obtain a algorithm to enumerate all the 3-edge-colourings of a connected cubic graph in time O ^?(2 ^n/2)=O ^?(1.4143 ⁿ ) and polynomial space. This improves the running time of O ^?(1.5423 ⁿ ) of the algorithm due to Golovach et al. (Proceedings of WG 2010, pp. 39–50, 2010). We also show that the number of 4-total-colourings of a connected cubic graph is at most 3?2^3n/2. Again, our proof yields a branching algorithm to enumerate all the 4-total-colourings of a connected cubic graph.     

L(2,1)-labelings of the edge-path-replacement of a graph

For two positive integers j and k with j≥k, an L(j,k)-labeling of a graph G is an assignment of nonnegative integers to V(G) such that the difference between labels of adjacent vertices is at least j, and the difference between labels of vertices that are distance two apart is at least k. The span of an L(j,k)-labeling of a graph G is the difference between the maximum and minimum integers used by it. The L(j,k)-labelings-number of G is the minimum span over all L(j,k)-labelings of G. This paper focuses on L(2,1)-labelings-number of the edge-path-replacement G(P _k ) of a graph G. Note that G(P ₃) is the incidence graph of G. L(2,1)-labelings of the edge-path-replacement G(P ₃) of a graph, called (2,1)-total labeling of G, was introduced by Havet and Yu in 2002 (Workshop graphs and algorithms, Dijon, France, 2003; Discrete Math. 308:498–513, 2008). They (Havet and Yu, Discrete Math. 308:498–513, 2008) obtain the bound $\Delta+1\leq\lambda^{T}_{2}(G)\leq2\Delta+1$ and conjectured $\lambda^{T}_{2}(G)\leq\Delta+3$ . In this paper, we obtain that λ(G(P _k ))≤Δ+2 for k≥5, and conjecture λ(G(P ₄))≤Δ+2 for any graph G with maximum degree Δ.