Parameterized dominating set problem in chordal graphs: complexity and lower bound

In this paper, we study the parameterized dominating set problem in chordal graphs. The goal of the problem is to determine whether a given chordal graph G=(V,E) contains a dominating set of size k or not, where k is an integer parameter. We show that the problem is W[1]-hard and it cannot be solved in time unless 3SAT can be solved in subexponential time. In addition, we show that the upper bound of this problem can be improved to when the underlying graph G is an interval graph.     

A solution to a conjecture on the generalized connectivity of graphs

The generalized k-connectivity \(\kappa _k(G)\) of a graph G was introduced by Chartrand et al. in (Bull Bombay Math Colloq 2:1–6, 1984), which is a nice generalization of the classical connectivity. Recently, as a natural counterpart, Li et al. proposed the concept of generalized edge-connectivity for a graph. In this paper, we consider the computational complexity of the generalized connectivity and generalized edge-connectivity of a graph. We give a confirmative solution to a conjecture raised by S. Li in Ph.D. Thesis (2012). We also give a polynomial-time algorithm to a problem of generalized k-edge-connectivity.     

A note on the minimum number of choosability of planar graphs

The problem of minimum number of choosability of graphs was first introduced by Vizing. It appears in some practical problems when concerning frequency assignment. In this paper, we study two important list coloring, list edge coloring and list total coloring. We prove that \(\chi '_{l}(G)=\varDelta \) and \(\chi ''_{l}(G)=\varDelta +1\) for planar graphs with \(\varDelta \ge 8\) and without adjacent 4-cycles.     

A linear-time algorithm for clique-coloring problem in circular-arc graphs

A maximal clique of G is a clique not properly contained in any other clique. A k-clique-coloring of a graph G is an assignment of k colors to the vertices of G such that no maximal clique with at least two vertices is monochromatic. The smallest integer k admitting a k-clique-coloring of G is called clique-coloring number of G. Cerioli and Korenchendler (Electron Notes Discret Math 35:287–292, 2009) showed that there is a polynomial-time algorithm to solve the clique-coloring problem in circular-arc graphs and asked whether there exists a linear-time algorithm to find an optimal clique-coloring in circular-arc graphs or not. In this paper we present a linear-time algorithm of the optimal clique-coloring in circular-arc graphs.     

Note on incidence chromatic number of subquartic graphs

An incidence in a graph G is a pair (v, e) where v is a vertex of G and e is an edge of G incident to v. Two incidences (v, e) and (u, f) are adjacent if at least one of the following holds: \((a) v = u, (b) e = f\), or \((c) vu \in \{e,f\}\). An incidence coloring of G is a coloring of its incidences assigning distinct colors to adjacent incidences. In this note we prove that every subquartic graph admits an incidence coloring with at most seven colors.     

The density maximization problem in graphs

We consider a framework for bi-objective network construction problems where one objective is to be maximized while the other is to be minimized. Given a host graph G=(V,E) with edge weights w _e ∈? and edge lengths ? _e ∈? for e∈E we define the density of a pattern subgraph H=(V′,E′)?G as the ratio ?(H)=∑ _e∈E′ w _e /∑ _e∈E′ ? _e . We consider the problem of computing a maximum density pattern H under various additional constraints. In doing so, we compute a single Pareto-optimal solution with the best weight per cost ratio subject to additional constraints further narrowing down feasible solutions for the underlying bi-objective network construction problem. First, we consider the problem of computing a maximum density pattern with weight at least W and length at most L in a host G. We call this problem the biconstrained density maximization problem. This problem can be interpreted in terms of maximizing the return on investment for network construction problems in the presence of a limited budget and a target profit. We consider this problem for different classes of hosts and patterns. We show that it is NP-hard, even if the host has treewidth 2 and the pattern is a path. However, it can be solved in pseudo-polynomial linear time if the host has bounded treewidth and the pattern is a graph from a given minor-closed family of graphs. Finally, we present an FPTAS for a relaxation of the density maximization problem, in which we are allowed to violate the upper bound on the length at the cost of some penalty. Second, we consider the maximum density subgraph problem under structural constraints on the vertex set that is used by the patterns. While a maximum density perfect matching can be computed efficiently in general graphs, the maximum density Steiner-subgraph problem, which requires a subset of the vertices in any feasible solution, is NP-hard and unlikely to admit a constant-factor approximation. When parameterized by the number of vertices of the pattern, this problem is W[1]-hard in general graphs. On the other hand, it is FPT on planar graphs if there is no constraint on the pattern and on general graphs if the pattern is a path.     

A solution approach to a synchronisation problem in a JIT production system

Delivering of orders on time, increasing productivity and reducing costs are all challenges that companies have to cope with on a regular basis. Making production lines compatible solves these problems and means a reduction in line stoppages and cycle time. In continuous production systems in which production is carried out in lots, the main ways to ensure an uninterrupted and smooth flow and have a high production rate, are line balancing and synchronising work stations. In this paper, a line stoppage and productivity problem at an automotive factory (Toyota Turkey plant, Sakarya city) is solved by root-cause analysis. Cycle time and in-process inventory inconsistency causes the problem between paint and assembly lines. Different solutions are researched and the most appropriate one is selected and implemented.     

Heterochromatic tree partition number in complete multipartite graphs

The heterochromatic tree partition number of an \(r\) -edge-colored graph \(G,\) denoted by \(t_r(G),\) is the minimum positive integer \(p\) such that whenever the edges of the graph \(G\) are colored with \(r\) colors, the vertices of \(G\) can be covered by at most \(p\) vertex disjoint heterochromatic trees. In this article we determine the upper and lower bounds for the heterochromatic tree partition number \(t_r(K_{n_1,n_2,\ldots ,n_k})\) of an \(r\) -edge-colored complete \(k\) -partite graph \(K_{n_1,n_2,\ldots ,n_k}\) , and the gap between upper and lower bounds is at most one.     

A combinatorial proof for the circular chromatic number of Kneser graphs

Chen (J Combin Theory A 118(3):1062–1071, 2011) confirmed the Johnson–Holroyd–Stahl conjecture that the circular chromatic number of a Kneser graph is equal to its chromatic number. A shorter proof of this result was given by Chang et al. (J Combin Theory A 120:159–163, 2013). Both proofs were based on Fan’s lemma (Ann Math 56:431–437, 1952) in algebraic topology. In this article we give a further simplified proof of this result. Moreover, by specializing a constructive proof of Fan’s lemma by Prescott and Su (J Combin Theory A 111:257–265, 2005), our proof is self-contained and combinatorial.     

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

An online trading problem with an increasing number of available products

Journal of Combinatorial Optimization - In this paper, we study a multiple time series search problem in which at the first n periods, one product is produced in each period and becomes sellable....     

Algorithms for the maximum k-club problem in graphs

Given a simple undirected graph G, a k-club is a subset of vertices inducing a subgraph of diameter at most k. The maximum k-club problem (MkCP) is to find a k-club of maximum cardinality in G. These structures, originally introduced to model cohesive subgroups in social network analysis, are of interest in network-based data mining and clustering applications. The maximum k-club problem is NP-hard, moreover, determining whether a given k-club is maximal (by inclusion) is NP-hard as well. This paper first provides a sufficient condition for testing maximality of a given k-club. Then it proceeds to develop a variable neighborhood search (VNS) heuristic and an exact algorithm for MkCP that uses the VNS solution as a lower bound. Computational experiments with test instances available in the literature show that the proposed algorithms are very effective on sparse instances and outperform the existing methods on most dense graphs from the testbed.     

The Steiner cycle and path cover problem on interval graphs

The Steiner path problem is a common generalization of the Steiner tree and the Hamiltonian path problem, in which we have to decide if for a given graph there exists a path visiting a fixed set of terminals. In the Steiner cycle problem we look for a cycle visiting all terminals instead of a path. The Steiner path cover problem is an optimization variant of the Steiner path problem generalizing the path cover problem, in which one has to cover all terminals with a minimum number of paths. We study those problems for the special class of interval graphs. We present linear time algorithms for both the Steiner path cover problem and the Steiner cycle problem on interval graphs given as endpoint sorted lists. The main contribution is a lemma showing that backward steps to non-Steiner intervals are never necessary. Furthermore, we show how to integrate this modification to the deferred-query technique of Chang et al. to obtain the linear running times.

     

The matching extension problem in general graphs is co-NP-complete

A simple connected graph G with 2n vertices is said to be k-extendable for an integer k with \(0<k<n\) if G contains a perfect matching and every matching of cardinality k in G is a subset of some perfect matching. Lakhal and Litzler (Inf Process Lett 65(1):11–16, 1998) discovered a polynomial algorithm that decides whether a bipartite graph is k-extendable. For general graphs, however, it has been an open problem whether there exists a polynomial algorithm. The new result presented in this paper is that the extendability problem is co-NP-complete.     

The maximum cardinality cut problem in co-bipartite chain graphs

A co-bipartite chain graph is a co-bipartite graph in which the neighborhoods of the vertices in each clique can be linearly ordered with respect to inclusion. It is known that the maximum cardinality cut problem (\({\textsc {MaxCut}}\)) is \({\textsc {NP}}{\text {-hard}}\) in co-bipartite graphs (Bodlaender and Jansen, Nordic J Comput 7(2000):14–31, 2000). We consider \({\textsc {MaxCut}}\) in co-bipartite chain graphs. We first consider the twin-free case and present an explicit solution. We then show that \({\textsc {MaxCut}}\) is polynomial time solvable in this graph class.     

On the total domination subdivision number in some classes of graphs

A set S of vertices of a graph G=(V,E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γ _t (G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number sd_gt(G)\mathrm {sd}_{\gamma_{t}}(G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. In this paper we prove that sd_gt(G) ￡ g_t(G)+1\mathrm {sd}_{\gamma_{t}}(G)\leq\gamma_{t}(G)+1 for some classes of graphs.