Improved upper bound for the degenerate and star chromatic numbers of graphs

Let \(G=G(V,E)\) be a graph. A proper coloring of G is a function \(f:V\rightarrow N\) such that \(f(x)\ne f(y)\) for every edge \(xy\in E\). A proper coloring of a graph G such that for every \(k\ge 1\), the union of any k color classes induces a \((k-1)\)-degenerate subgraph is called a degenerate coloring; a proper coloring of a graph with no two-colored \(P_{4}\) is called a star coloring. If a coloring is both degenerate and star, then we call it a degenerate star coloring of graph. The corresponding chromatic number is denoted as \(\chi _{sd}(G)\). In this paper, we employ entropy compression method to obtain a new upper bound \(\chi _{sd}(G)\le \lceil \frac{19}{6}\Delta ^{\frac{3}{2}}+5\Delta \rceil \) for general graph G.     

Neighbor sum distinguishing index of 2-degenerate graphs

We consider proper edge colorings of a graph G using colors in \(\{1,\ldots ,k\}\). Such a coloring is called neighbor sum distinguishing if for each pair of adjacent vertices u and v, the sum of the colors of the edges incident with u is different from the sum of the colors of the edges incident with v. The smallest value of k in such a coloring of G is denoted by \({\mathrm ndi}_{\Sigma }(G)\). In this paper we show that if G is a 2-degenerate graph without isolated edges, then \({\mathrm ndi}_{\Sigma }(G)\le \max \{\Delta (G)+2,7\}\).     

Multiple facility location on a network with linear reliability order of edges

We study the problem of locating facilities on the nodes of a network to maximize the expected demand serviced. The edges of the input graph are subject to random failure due to a disruptive event. We consider a special type of failure correlation. The edge dependency model assumes that the failure of a more reliable edge implies the failure of all less reliable ones. Under this dependency model called Linear Reliability Order (LRO) we give two polynomial time exact algorithms. When two distinct LRO’s exist, we prove the total unimodularity of a linear programming formulation. In addition, we show that minimizing the sum of facility opening costs and expected cost of unserviced demand under two orderings reduces to a matching problem. We prove NP-hardness of the three orderings case and show that the problem with an arbitrary number of orderings generalizes the deterministic maximum coverage problem. When a demand point can be covered only if a facility exists within a distance limit, we show that the problem is NP-hard even for a single ordering.     

On global integer extrema of real-valued box-constrained multivariate quadratic functions

Determining global integer extrema of an real-valued box-constrained multivariate quadratic functions is a very difficult task. In this paper, we present an analytic method, which is based on a combinatorial optimization approach in order to calculate global integer extrema of a real-valued box-constrained multivariate quadratic function, whereby this problem will be proven to be as NP-hard via solving it by a Travelling Salesman instance. Instead, we solve it using eigenvalue theory, which allows us to calculate the eigenvalues of an arbitrary symmetric matrix using Newton’s method, which converges quadratically and in addition yields a Jordan normal form with \(1 \times 1\)-blocks, from which a special representation of the multivariate quadratic function based on affine linear functions can be derived. Finally, global integer minimizers can be calculated dynamically and efficiently most often in a small amount of time using the Fourier–Motzkin- and a Branch and Bound like Dijkstra-algorithm. As an application, we consider a box-constrained bivariate and multivariate quadratic function with ten arguments.     

Parameterized algorithms for min–max 2-cluster editing

For a given graph and an integer t, the Min–Max 2-Clustering problem asks if there exists a modification of a given graph into two maximal disjoint cliques by inserting or deleting edges such that the number of the editing edges incident to each vertex is at most t. It has been shown that the problem can be solved in polynomial time for \(t<n/4\), where n is the number of vertices. In this paper, we design parameterized algorithms for different ranges of t. Let \(k=t-n/4\). We show that the problem is polynomial-time solvable when roughly \(k<\sqrt{n/32}\). When \(k\in o(n)\), we design a randomized and a deterministic algorithm with sub-exponential time parameterized complexity, i.e., the problem is in SUBEPT. We also show that the problem can be solved in \(O({2}^{n/r}\cdot n^2)\) time for \(k<n/12\) and in \(O(n^2\cdot 2^{3n/4+k})\) time for \(n/12\le k< n/4\), where \(r=2+\lfloor (n/4-3k-2)/(2k+1) \rfloor \ge 2\).     

Characterizations of <Emphasis Type="Italic">k</Emphasis>-cutwidth critical trees

The cutwidth problem for a graph G is to embed G into a path such that the maximum number of overlap edges (i.e., the congestion) is minimized. The investigations of critical graphs and their structures are meaningful in the study of a graph-theoretic parameters. We study the structures of k-cutwidth \((k>1)\) critical trees, and use them to characterize the set of all 4-cutwidth critical trees.     

The Weight Function Lemma for graph pebbling

Graph pebbling is a network model for studying whether or not a given supply of discrete pebbles can satisfy a given demand via pebbling moves. A pebbling move across an edge of a graph takes two pebbles from one endpoint and places one pebble at the other endpoint; the other pebble is lost in transit as a toll. It has been shown that deciding whether a supply can meet a demand on a graph is NP-complete. The pebbling number of a graph is the smallest t such that every supply of t pebbles can satisfy every demand of one pebble byt a vertex. Deciding if the pebbling number is at most k is \(\Pi _2^\mathsf{P}\)-complete. In this paper we develop a tool, called the Weight Function Lemma, for computing upper bounds and sometimes exact values for pebbling numbers with the assistance of linear optimization. With this tool we are able to calculate the pebbling numbers of much larger graphs than in previous algorithms, and much more quickly as well. We also obtain results for many families of graphs, in many cases by hand, with much simpler and remarkably shorter proofs than given in previously existing arguments (certificates typically of size at most the number of vertices times the maximum degree), especially for highly symmetric graphs. Here we apply the Weight Function Lemma to several specific graphs, including the Petersen, Lemke, \(4\mathrm{th}\) weak Bruhat, and Lemke squared, as well as to a number of infinite families of graphs, such as trees, cycles, graph powers of cycles, cubes, and some generalized Petersen and Coxeter graphs. In doing so we partly answer a question of Pachter, et al., by computing the pebbling exponent of cycles to within an asymptotically small range. It is conceivable that this method yields an approximation algorithm for graph pebbling.     

Is there any polynomial upper bound for the universal labeling of graphs?

A universal labeling of a graph G is a labeling of the edge set in G such that in every orientation \(\ell \) of G for every two adjacent vertices v and u, the sum of incoming edges of v and u in the oriented graph are different from each other. The universal labeling number of a graph G is the minimum number k such that G has universal labeling from \(\{1,2,\ldots , k\}\) denoted it by \(\overrightarrow{\chi _{u}}(G) \). We have \(2\Delta (G)-2 \le \overrightarrow{\chi _{u}} (G)\le 2^{\Delta (G)}\), where \(\Delta (G)\) denotes the maximum degree of G. In this work, we offer a provocative question that is: “Is there any polynomial function f such that for every graph G, \(\overrightarrow{\chi _{u}} (G)\le f(\Delta (G))\)?”. Towards this question, we introduce some lower and upper bounds on their parameter of interest. Also, we prove that for every tree T, \(\overrightarrow{\chi _{u}}(T)={\mathcal {O}}(\Delta ^3) \). Next, we show that for a given 3-regular graph G, the universal labeling number of G is 4 if and only if G belongs to Class 1. Therefore, for a given 3-regular graph G, it is an \( {{\mathbf {N}}}{{\mathbf {P}}} \)-complete to determine whether the universal labeling number of G is 4. Finally, using probabilistic methods, we almost confirm a weaker version of the problem.     

On the odd girth and the circular chromatic number of generalized Petersen graphs

A class \(\mathcal{G}\) of simple graphs is said to be girth-closed (odd-girth-closed) if for any positive integer g there exists a graph \(\mathrm {G} \in \mathcal{G}\) such that the girth (odd-girth) of \(\mathrm {G}\) is \(\ge g\). A girth-closed (odd-girth-closed) class \(\mathcal{G}\) of graphs is said to be pentagonal (odd-pentagonal) if there exists a positive integer \(g^*\) depending on \(\mathcal{G}\) such that any graph \(\mathrm {G} \in \mathcal{G}\) whose girth (odd-girth) is greater than \(g^*\) admits a homomorphism to the five cycle (i.e. is \(\mathrm {C}_{_{5}}\)-colourable). Although, the question “Is the class of simple 3-regular graphs pentagonal?” proposed by Ne?et?il (Taiwan J Math 3:381–423, 1999) is still a central open problem, Gebleh (Theorems and computations in circular colourings of graphs, 2007) has shown that there exists an odd-girth-closed subclass of simple 3-regular graphs which is not odd-pentagonal. In this article, motivated by the conjecture that the class of generalized Petersen graphs is odd-pentagonal, we show that finding the odd girth of generalized Petersen graphs can be transformed to an integer programming problem, and using the combinatorial and number theoretic properties of this problem, we explicitly compute the odd girth of such graphs, showing that the class is odd-girth-closed. Also, we obtain upper and lower bounds for the circular chromatic number of these graphs, and as a consequence, we show that the subclass containing generalized Petersen graphs \(\mathrm {Pet}(n,k)\) for which either k is even, n is odd and \(n\mathop {\equiv }\limits ^{k-1}\pm 2\) or both n and k are odd and \(n\ge 5k\) is odd-pentagonal. This in particular shows the existence of nontrivial odd-pentagonal subclasses of 3-regular simple graphs.     

Total completion time minimization in online hierarchical scheduling of unit-size jobs

This paper investigates an online hierarchical scheduling problem on m parallel identical machines. Our goal is to minimize the total completion time of all jobs. Each job has a unit processing time and a hierarchy. The job with a lower hierarchy can only be processed on the first machine and the job with a higher hierarchy can be processed on any one of m machines. We first show that the lower bound of this problem is at least \(1+\min \{\frac{1}{m}, \max \{\frac{2}{\lceil x\rceil +\frac{x}{\lceil x\rceil }+3}, \frac{2}{\lfloor x\rfloor +\frac{x}{\lfloor x\rfloor }+3}\}\), where \(x=\sqrt{2m+4}\). We then present a greedy algorithm with tight competitive ratio of \(1+\frac{2(m-1)}{m(\sqrt{4m-3}+1)}\). The competitive ratio is obtained in a way of analyzing the structure of the instance in the worst case, which is different from the most common method of competitive analysis. In particular, when \(m=2\), we propose an optimal online algorithm with competitive ratio of \(16\) \(/\) \(13\), which complements the previous result which provided an asymptotically optimal algorithm with competitive ratio of 1.1573 for the case where the number of jobs n is infinite, i.e., \(n\rightarrow \infty \).