Search

A k -class domination coloring (k -cd-coloring) is a partition of the vertex set of a graph G into k independent sets V 1 , ... , V k , where each V i is dominated by some vertex u i of G. The least integer k such that G admits a k -cd-coloring is called the cd-chromatic number, χ c d (G) , of G. A subset S of the vertex set of a graph G is called a subclique in G if d G (x , y) ≠ 2 for every x , y ∈ S. The cardinality of a maximum subclique in G is called the subclique number, ω s (G) , of G. In this paper, we present algorithms to compute an optimal cd-coloring and a maximum subclique of (i) trees with time complexity O (n) and (ii) co-bipartite graphs with time complexity O (n 2. 5). This improves O (n 3) algorithms by Shalu et al. (2017, 2020). In addition, we prove tight upper bounds for the subclique number of the class of (i) P 5 -free graphs and (ii) double-split graphs. [ABSTRACT FROM AUTHOR]

In this paper we study the parameterized complexity for the Maximum Happy Set problem (MaxHS): For an undirected graph G = (V , E) and a subset S ⊆ V of vertices, a vertex v is happy if v and all its neighbors are in S ; otherwise unhappy. Given an undirected graph G = (V , E) and an integer k , the goal of MaxHS is to find a subset S ⊆ V of k vertices such that the number of happy vertices is maximized. In this paper we first show that MaxHS is W[1]-hard with respect to k even if the input graph is a split graph. Then, we prove the fixed-parameter tractability of MaxHS when parameterized by tree-width, by clique-width plus k , by neighborhood diversity, or by cluster deletion number. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of determining all optimal integer solutions of a linear integer network flow problem, which we call the all optimal integer flow (AOF) problem. We derive an O (F (m + n) + m n + M) time algorithm to determine all F many optimal integer flows in a directed network with n nodes and m arcs, where M is the best time needed to find one minimum cost flow. We remark that stopping Hamacher's well-known method for the determination of the K best integer flows (Hamacher, 1995) at the first sub-optimal flow results in an algorithm with a running time of O (F m (n log n + m) + M) for solving the AOF problem. Our improvement is essentially made possible by replacing the shortest path sub-problem with a more efficient way to determine a so-called proper zero cost cycle using a modified depth-first search technique. As a byproduct, our analysis yields an enhanced algorithm to determine the K best integer flows that runs in O (K n 3 + M). Besides, we give lower and upper bounds for the number of all optimal integer and feasible integer solutions. Our bounds are based on the fact that any optimal solution can be obtained by an initial optimal tree solution plus a conical combination of incidence vectors of all induced cycles with bounded coefficients. [ABSTRACT FROM AUTHOR]

In Chirkov et al., (2019), classes of conic and discrete conic functions were introduced. In this paper we use the term convic instead conic. The class of convic functions properly includes the classes of convex functions, strictly quasiconvex functions and the class of quasiconvex polynomials. On the other hand, the class of convic functions is properly included in the class of quasiconvex functions. The discrete convic function is a discrete analogue of the convic function. In Chirkov et al., (2019), the lower bound 3 n − 1 log (2 ρ − 1) for the number of calls to the comparison oracle needed to find the minimum of the discrete convic function defined on integer points of some n -dimensional ball with radius ρ was obtained. But the problem of the existence of a polynomial (in log ρ for fixed n) algorithm for minimizing such functions has remained open. In this paper, we answer positively the question of the existence of such an algorithm. Namely, we propose an algorithm for minimizing discrete convic functions that uses 2 O (n 2 log n) log ρ calls to the comparison oracle and has 2 O (n 2 log n) poly (log ρ) bit complexity. [ABSTRACT FROM AUTHOR]

Given a real number α ∈ (0 , 1) , we define the Webster sequence of density α to be W α = (⌈ (n − 1 / 2) / α ⌉) n ∈ N , where ⌈ x ⌉ is the ceiling function. It is known that if α and β are irrational with α + β = 1 , then W α and W β partition N. On the other hand, an analogous result for three-part partitions does not hold: There does not exist a partition of N into sequences W α , W β , W γ with α , β , γ irrational. In this paper, we consider the question of how close one can come to a three-part partition of N into Webster sequences with prescribed densities α , β , γ. We show that if α , β , γ are irrational with α + β + γ = 1 , there exists a partition of N into sequences of densities α , β , γ , in which one of the sequences is a Webster sequence and the other two are "almost" Webster sequences that are obtained from Webster sequences by perturbing some elements by at most 1. We also provide two efficient algorithms to construct such partitions. The first algorithm outputs the n th element of each sequence in O (1) time and the second algorithm gives the assignment of the m th positive integer to a sequence in O (1) time. We show that the results are best-possible in several respects. Moreover, we describe applications of these results to apportionment and optimal scheduling problems. [ABSTRACT FROM AUTHOR]

In the 4-Path Vertex Cover problem, the input is an undirected graph G and an integer k. The goal is to decide whether there is a set S of vertices of size at most k such that every path with 4 vertices in G contains at least one vertex of S. In this paper we give a parameterized algorithm for 4-Path Vertex Cover whose time complexity is 2. 61 9 k ⋅ n O (1) , where n denotes the number of vertices of the input graph. [ABSTRACT FROM AUTHOR]

In the paper we introduce and study partitions of vectors in N p , as a natural extension of the classical partitions of integers. We show that these vector partitions are the suitable combinatorial notion in extending the Faà di Bruno formula to a general multi-variable setting, as well as in generalizing Bell polynomials. The Adomian polynomials can be obtained from this framework as a particular case. We also give a recursive algorithm which is proved to generate all the vector partitions without repetitions, and which can be used in numerical applications of extended Faà di Bruno formulae and generalized Bell polynomials. [ABSTRACT FROM AUTHOR]

Abstract A planar graph can be drawn without edge crossings in the plane. It is well known that testing planarity of a graph can be solved in linear time. A graph is 1-planar, if it admits a 1-planar embedding, where each edge has at most one crossing. Testing 1-planarity of a graph is known to be NP-complete. This paper initiates the problem of testing 2-planarity of a graph, in particular, testing "full-outer-2-planarity" of a graph. A graph is outer- k -planar for an integer k ≥ 0 , if it admits an outer- k -planar embedding , that is, every vertex is on the outer boundary and no edge has more than k crossings. A graph is full-outer- k -planar , if it admits a full-outer- k -planar embedding , that is, an outer- k -planar embedding such that no crossing appears along the outer boundary. We present several structural properties of triconnected outer-2-planar graphs and full-outer-2-planar graphs, and prove that every triconnected full-outer-2-planar graph has a constant number of full-outer-2-planar embeddings. Based on these properties, we present linear-time algorithms for testing full-outer-2-planarity of a graph G , where G is connected, biconnected or triconnected. The algorithm also produces a full-outer-2-planar embedding of a graph, if it exists. Moreover, we show that every outer- k -planar embedding admits a straight-line drawing. [ABSTRACT FROM AUTHOR]

Abstract Circle graphs are intersection graphs of chords in a circle and k -polygon graphs are intersection graphs of chords in a convex k -sided polygon where each chord has its endpoints on distinct sides. The k -polygon graphs, for k ≥ 2 , form an infinite chain of graph classes, each of which contains the class of permutation graphs. The union of all of those graph classes is the class of circle graphs. The polygon number ψ (G) of a circle graph G is the minimum k such that G is a k -polygon graph. Given a circle graph G and an integer k , determining whether ψ (G) ≤ k is NP-complete, while the problem is solvable in polynomial time for fixed k. In this paper, we show that ψ (G) is always at least as large as the asteroidal number of G , and equal to the asteroidal number of G when G is a connected distance hereditary graph that is not a clique. This implies that the classes of distance hereditary permutation graphs and distance hereditary AT-free graphs are the same, and we give a forbidden subgraph characterization of that class. We also establish the following upper bounds: ψ (G) is at most the clique cover number of G if G is not a clique, at most 1 plus the independence number of G , and at most ⌈ n ∕ 2 ⌉ where n ≥ 3 is the number of vertices of G. Our results lead to linear time algorithms for finding the minimum number of corners that must be added to a given circle representation to produce a polygon representation, and for finding the asteroidal number of a distance hereditary graph, both of which are improvements over previous algorithms for those problems. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to present an algebraic algorithm for solving parametric integer programs. Parametric integer programs are important for compiler optimization problems and many combinatorial problems. We will show the efficiency of our algebraic method. [ABSTRACT FROM AUTHOR]

Abstract: This paper studies a variation of domination in graphs called rainbow domination. For a positive integer , a -rainbow dominating function of a graph is a function such that for any vertex with . The -rainbow domination number of is the minimum value of , where runs over all -rainbow dominating functions of . A related concept is as follows. A weak -dominating function of is a function such that for any vertex with . The weak -domination number of is the minimum value of , where runs over all weak -dominating functions of . In this paper, we prove that for any strongly chordal graph . Our approach is a more general setting called the -function, which leads to interesting results on other variations of domination. We also give a linear-time algorithm for finding the weak -domination numbers of block graphs. [Copyright &y& Elsevier]

This paper considers the problem of many-to-many disjoint paths in the hypercube Q n with f faulty vertices and obtains the following result. For any integer k with 1 ≤ k ≤ n − 1 and any two sets S and T of k fault-free vertices in different partite sets of Q n ( n ≥ 2 ) , if f ≤ 2 n − 2 k − 2 and each fault-free vertex has at least two fault-free neighbors, then there exist k fully disjoint fault-free paths linking S and T which contain at least 2 n − 2 f vertices. A linear algorithm for finding such disjoint paths is also given. This result improves some known results in a sense. [ABSTRACT FROM AUTHOR]

Abstract: For a fixed positive integer , a -tuple total dominating set of a graph is a set such that every vertex of is adjacent to at least vertices in . The -tuple total domination problem is to determine a minimum -tuple total dominating set of . This paper studies -tuple total domination from an algorithmic point of view. In particular, we present a linear-time algorithm for the -tuple total domination problem for graphs in which each block is a clique, a cycle or a complete bipartite graph, which include trees, block graphs, cacti and block-cactus graphs. We also establish NP-hardness of the -tuple total domination problem in undirected path graphs. [Copyright &y& Elsevier]

Abstract: Given an edge weighted undirected graph and a positive integer , the Min-Degree Constrained Minimum Spanning Tree Problem (MDMST) consists of finding a minimum cost spanning tree of , such that each vertex is either a leaf or else has degree at least in the tree. In this paper, we discuss two formulations for MDMST based on exponentially many undirected and directed subtour breaking constraints and compare the strength of their Linear Programming (LP) bounds with other bounds in the literature. Aiming to overcome the fact that the strongest of the two models, the directed one, is not symmetric with respect to the LP bounds, we also presented a symmetric compact reformulation, devised with the application of an Intersection Reformulation Technique to the directed model. The reformulation proved to be much stronger than the previous models, but evaluating its bounds is very time consuming. Thus, better computational results were obtained by a Branch-and-cut algorithm based on the original directed formulation. With the proposed method, several new optimality certificates and new best upper bounds for MDMST were provided. [Copyright &y& Elsevier]

Abstract: For a positive integer , a -dominating set of a graph is a subset such that every vertex not in is adjacent to at least vertices in . The -domination problem is to determine a minimum -dominating set of . This paper studies the -domination problem in graphs from an algorithmic point of view. In particular, we present a linear-time algorithm for the -domination problem for graphs in which each block is a clique, a cycle or a complete bipartite graph. This class of graphs includes trees, block graphs, cacti and block-cactus graphs. We also establish NP-completeness of the -domination problem in split graphs. [Copyright &y& Elsevier]

Abstract: A set of a graph is a liar’s dominating set if for all , and for every pair of distinct vertices, . A graph admits a liar’s dominating set if each of its connected component has at least three vertices. Given a graph and an integer , the liar’s domination decision problem (LR-DOMDP) is to decide whether has a liar’s dominating set of cardinality at most . Slater [P.J. Slater, Liar’s Domination, Networks, 54(2) (2009) 70–74] proved that the LR-DOMDP is NP-complete for general graphs. Subsequently, Roden and Slater [M.L. Roden and P.J. Slater, Liar’s domination in graphs, Discrete Math., 309(19) (2009) 5884–5890] showed a more general family of problems to each be NP-complete for bipartite graphs. Besides this result, no other algorithmic result for the liar’s dominating set problem is available in the literature. In this paper, we first strengthen the complexity result of the LR-DOMDP by showing that this problem remains NP-complete for split graphs and hence for chordal graphs. Finally, we propose a linear time algorithm for computing a minimum cardinality liar’s dominating set in a tree. [Copyright &y& Elsevier]

Abstract: Given a positive integer and an undirected edge-weighted connected simple graph with at least edges of positive weight, we wish to partition the graph into edge-disjoint connected components of approximately the same size. We focus on the max-min ratio of the partition, which is the weight of the maximum component divided by that of the minimum component. It has been shown that for some instances, the max-min ratio is at least two. In this paper, for any graph with no edge weight larger than one half of the average weight, we provide a linear-time algorithm for delivering a partition with max-min ratio at most two. Furthermore, by an extreme example, we show that the above restriction on edge weights is the loosest possible. [Copyright &y& Elsevier]