Minimal path decomposition of complete bipartite graphs

This paper deals with the subject of minimal path decomposition of complete bipartite graphs. A path decomposition of a graph is a decomposition of it into simple paths such that every edge appears in exactly one path. If the number of paths is the minimum possible, the path decomposition is called minimal. Algorithms that derive such decompositions are presented, along with their proof of correctness, for the three out of the four possible cases of a complete bipartite graph.     

A Nordhaus-Gaddum-type result for the induced path number

The induced path number ??(G) of a graph G is defined as the minimum number of subsets into which the vertex set of G can be partitioned so that each subset induces a graph. A Nordhaus-Gaddum-type result is a (tight) lower or upper bound on the sum (or product) of a parameter of a graph and its complement. If G is a subgraph of H, then the graph H?E(G) is the complement of G relative to H. In this paper, we consider Nordhaus-Gaddum-type results for the parameter ?? when the relative complement is taken with respect to the complete bipartite graph K _n,n .     

The determination of the least distance to the strongly efficient frontier in Data Envelopment Analysis oriented models: Modelling and computational aspects

Determining the least distance to the efficient frontier for estimating technical inefficiency, with the consequent determination of closest targets, has been one of the relevant issues in recent Data Envelopment Analysis literature. This new paradigm contrasts with traditional approaches, which yield furthest targets. In this respect, some techniques have been proposed in order to implement the new paradigm. A group of these techniques is based on identifying all the efficient faces of the polyhedral production possibility set and, therefore, is associated with the resolution of a NP-hard problem. In contrast, a second group proposes different models and particular algorithms to solve the problem avoiding the explicit identification of all these faces. These techniques have been applied more or less successfully. Nonetheless, the new paradigm is still unsatisfactory and incomplete to a certain extent. One of these challenges is that related to measuring technical inefficiency in the context of oriented models, i.e., models that aim at changing inputs or outputs but not both. In this paper, we show that existing specific techniques for determining the least distance without identifying explicitly the frontier structure for graph measures, which change inputs and outputs at the same time, do not work for oriented models. Consequently, a new methodology for satisfactorily implementing these situations is proposed. Finally, the new approach is empirically checked by using a recent PISA database consisting of 902 schools.     

A complexity dichotomy and a new boundary class for the dominating set problem

We study the computational complexity of the dominating set problem for hereditary graph classes, i.e., classes of simple unlabeled graphs closed under deletion of vertices. Every hereditary class can be defined by a set of its forbidden induced subgraphs. There are numerous open cases for the complexity of the problem even for hereditary classes with small forbidden structures. We completely determine the complexity of the problem for classes defined by forbidding a five-vertex path and any set of fragments with at most five vertices. Additionally, we also prove polynomial-time solvability of the problem for some two classes of a similar type. The notion of a boundary class is a helpful tool for analyzing the computational complexity of graph problems in the family of hereditary classes. Three boundary classes were known for the dominating set problem prior to this paper. We present a new boundary class for it.     

Technology adoption and training practices as a constrained shortest path problem

Technology adoption is not a new venue for research. Much work of decision modeling, diffusion of new technology and statistical analysis of survey data has been done. Some studies focus on finding the optimal forms of technology to adopt within a complementarity framework, but there is no mention of finding an optimal path from a firm's current state to its optimal state. This represents a significant gap in the literature. The paper applies a constrained shortest path problem to training and technology adoption decisions by firms. Given the current set of training and technology adoption the method solves for what technology/practice should be adopted or removed from the complete set of combinations and in what order so as to maximize performance subject to budget constraints. To the authors' knowledge, this is the first application of the constrained shortest path problem to technology adoption decisions.     

k-tuple total domination in cross products of graphs

For k??1 an integer, a set S of vertices in a graph G with minimum degree at least?k is a k-tuple total dominating set of G if every vertex of G is adjacent to at least k vertices in S. The minimum cardinality of a k-tuple total dominating set of G is the k-tuple total domination number of G. When k=1, the k-tuple total domination number is the well-studied total domination number. In this paper, we establish upper and lower bounds on the k-tuple total domination number of the cross product graph G×H for any two graphs G and H with minimum degree at least?k. In particular, we determine the exact value of the k-tuple total domination number of the cross product of two complete graphs.     

On the vertex cover $$P_3$$ problem parameterized by treewidth

Consider a graph G. A subset of vertices, F, is called a vertex cover \(P_t\) (\(VCP_t\)) set if every path of order t contains at least one vertex in F. Finding a minimum \(VCP_t\) set in a graph is is NP-hard for any integer \(t\ge 2\) and is called the \(MVCP_3\) problem. In this paper, we study the parameterized algorithms for the \(MVCP_3\) problem when the underlying graph G is parameterized by the treewidth. Given an n-vertex graph together with its tree decomposition of width at most p, we present an algorithm running in time \(4^{p}\cdot n^{O(1)}\) for the \(MVCP_3\) problem. Moreover, we show that for the \(MVCP_3\) problem on planar graphs, there is a subexponential parameterized algorithm running in time \(2^{O(\sqrt{k})}\cdot n^{O(1)}\) where k is the size of the optimal solution.     

The competition number of a graph with?exactly?two?holes

Given an acyclic digraph D, the competition graph C(D) of D is the graph with the same vertex set as D and two distinct vertices x and y are adjacent in C(D) if and only if there is a vertex v in D such that (x,v) and (y,v) are arcs of D. The competition number κ(G) of a graph G is the least number of isolated vertices that must be added to G to form a competition graph. The purpose of this paper is to prove that the competition number of a graph with exactly two holes is at most three.     

Parental bereavement: a panoramic view

This study is aimed at identifying central themes of bereavement. A qualitative approach was employed in the analyses of interviews with 22 bereaved parents. The analyses yielded four central issues or themes of bereavement, each with its own set of sub-themes or categories, as the narrative demanded. The first of these themes, pertaining to the life of the family before the death of a child had taken place, was named the risk factor. Circumstances leading up to the death, surrounding the death, the cause of death, and the events following the death were coded as bereavement circumstances. The grief reactions codes were divided into categories of emotional, physical, behavioral, relational, spiritual, and cognitive reactions, as described by the participants. Finally, the mourning codes described the mechanisms employed by the participants in their attempts to survive and continue living after the death. These findings can be used in the training of support workers and the development of bereavement interventions.     

Minimum power assignment in wireless ad hoc networks with spanner property

Power assignment for wireless ad hoc networks is to assign a power for each wireless node such that the induced communication graph has some required properties. Recently research efforts have focused on finding the minimum power assignment to guarantee the connectivity or fault-tolerance of the network. In this paper, we study a new problem of finding the power assignment such that the induced communication graph is a spanner for the original communication graph when all nodes have the maximum power. Here, a spanner means that the length of the shortest path in the induced communication graph is at most a constant times of the length of the shortest path in the original communication graph. Polynomial time algorithm is given to minimize the maximum assigned power with spanner property. The algorithm also works for any other property that can be tested in polynomial time and is monotone. We then give a polynomial time approximation method to minimize the total transmission radius of all nodes. Finally, we propose two heuristics and conduct extensive simulations to study their performance when we aim to minimize the total assigned power of all nodes. The author is partially supported by NSF CCR-0311174.     

Characterisation of forests with trivial game domination numbers

In the domination game, two players, the Dominator and Staller, take turns adding vertices of a fixed graph to a set, at each turn increasing the number of vertices dominated by the set, until the final set \(A_*\) dominates the whole graph. The Dominator plays to minimise the size of the set \(A_*\) while the Staller plays to maximise it. A graph is \(D\)-trivial if when the Dominator plays first and both players play optimally, the set \(A_*\) is a minimum dominating set of the graph. A graph is \(S\)-trivial if the same is true when the Staller plays first. We consider the problem of characterising \(D\)-trivial and \(S\)-trivial graphs. We give complete characterisations of \(D\)-trivial forests and of \(S\)-trivial forests. We also show that \(2\)-connected \(D\)-trivial graphs cannot have large girth, and conjecture that the same holds without the connectivity condition.     

Tagged Probe Interval Graphs

A generalization of interval graph is introduced for cosmid contig mapping of DNA. A graph is a tagged probe interval graph if its vertex set can be partitioned into two subsets of probes and nonprobes, and a closed interval can be assigned to each vertex such that two vertices are adjacent if and only if at least one of them is a probe and one end of its corresponding interval is contained in the interval corresponding to the other vertex. We show that tagged probe interval graphs are weakly triangulated graphs, hence are perfect graphs. For a tagged probe interval graph with a given partition, we give a chordal completion that is consistent to any interval completions with respect to the same vertex partition.     

On the complexity of path problems in properly colored directed graphs

We address the complexity class of several problems related to finding a path in a properly colored directed graph. A properly colored graph is defined as a graph G whose vertex set is partitioned into $\mathcal{X}(G)$ stable subsets, where $\mathcal{X}(G)$ denotes the chromatic number of G. We show that to find a simple path that meets all the colors in a properly colored directed graph is NP-complete, and so are the problems of finding a shortest and longest of such paths between two specific nodes.     

A simplified algorithm for the all pairs shortest path problem with O(n 2logn) expected time

The best known expected time for the all pairs shortest path problem on a directed graph with non-negative edge costs is O(n ²logn) by Moffat and Takaoka. Let the solution set be the set of vertices to which the given algorithm has so far established shortest paths. The Moffat-Takaoka algorithm maintains complexities before and after the critical point in balance, which is the moment when the size of the solution set is n?n/logn. In this paper, we remove the concept of critical point, whereby we make the algorithm simpler and seamless, resulting in a simpler analysis.     

On Split-Coloring Problems

We study a new coloring concept which generalizes the classical vertex coloring problem in a graph by extending the notion of stable sets to split graphs. First of all, we propose the packing problem of finding the split graph of maximum size where a split graph is a graph G = (V,E) in which the vertex set V can be partitioned into a clique K and a stable set S. No condition is imposed on the edges linking vertices in S to the vertices in K. This maximum split graph problem gives rise to an associated partitioning problem that we call the split-coloring problem. Given a graph, the objective is to cover all his vertices by a least number of split graphs. Definitions related to this new problem are introduced. We mention some polynomially solvable cases and describe open questions on this area. An erratum to this article is available at .     

Vertices in all minimum paired-dominating sets of?block graphs

Let G=(V,E) be a simple graph without isolated vertices. A set S?V is a paired-dominating set if every vertex in V?S has at least one neighbor in S and the subgraph induced by S contains a perfect matching. In this paper, we present a linear-time algorithm to determine whether a given vertex in a block graph is contained in all its minimum paired-dominating sets.     

Super-cyclically edge-connected regular graphs

A cyclic edge-cut of a 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. We call a cyclically separable graph super cyclically edge-connected, in short, super-λ _c , if the removal of any minimum cyclic edge-cut results in a component which is a shortest cycle. In Z. Zhang, B. Wang (Super cyclically edge-connected transitive graphs, J. Combin. Optim. 22:549–562, 2011), it is proved that a connected edge-transitive graph is super-λ _c if either G is cubic with girth at least 7 or G has minimum degree at least 4 and girth at least 6, and the authors also conjectured that a connected graph which is both vertex-transitive and edge-transitive is always super cyclically edge-connected. In this article, for a λ _c -optimal but not super-λ _c graph G, all possible λ _c -superatoms of G which have non-empty intersection with other λ _c -superatoms are determined. This is then used to give a complete classification of non-super-λ _c edge-transitive k(k≥3)-regular graphs.     

Finding a contra-risk path between two nodes in undirected graphs

Given an undirected graph with a source node s and a sink node t. The anti-risk path problem is defined as the problem of finding a path between node s to node t with the least risk under the assumption that at most one edge of each path may be blocked. Xiao et al. (J Comb Optim 17:235–246, 2009) defined the problem and presented an \(O(mn+n^2 \log n)\) time algorithm to find an anti-risk path, where n and m are the number of nodes and edges, respectively. Recently, Mahadeokar and Saxena (J Comb Optim 27:798–807, 2014) solved the problem in \(O(m+n \log n)\) time. In this paper, first, a new version of the anti-risk path (called contra-risk path) is defined, which is more effective than an anti-risk path in many networks. Then, an algorithm to find a contra-risk path is presented, which runs in \(O(m+n \log n)\) time.     

Implementation with Near‐Complete Information

Many refinements of Nash equilibrium yield solution correspondences that do not have closed graph in the space of payoffs or information. This has significance for implementation theory, especially under complete information. If a planner is concerned that all equilibria of his mechanism yield a desired outcome, and entertains the possibility that players may have even the slightest uncertainty about payoffs, then the planner should insist on a solution concept with closed graph. We show that this requirement entails substantial restrictions on the set of implementable social choice rules. In particular, when preferences are strict (or more generally, hedonic), while almost any social choice function can be implemented in undominated Nash equilibrium, only monotonic social choice functions can be implemented in the closure of the undominated Nash correspondence.     

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.