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.     

Even factors of graphs

An even factor of a graph is a spanning subgraph in which each vertex has a positive even degree. Favaron and Kouider (J Gr Theory 77:58–67, 2014) showed that if a simple graph G has an even factor, then it has an even factor F with \(|E(F)| \ge \frac{7}{16} (|E(G)| + 1)\). This ratio was improved to \(\frac{4}{7}\) recently by  Chen and Fan (J Comb Theory Ser B 119:237–244, 2016), which is the best possible. In this paper, we take the set of vertices of degree 2 (say \(V_{2}(G)\)) into consideration and further strengthen this lower bound. Our main result is to show that for any simple graph G having an even factor, G has an even factor F with \(|E(F)| \ge \frac{4}{7} (|E(G)| + 1)+\frac{1}{7}|V_{2}(G)|\).     

A note on optimal pebbling of hypercubes

A pebbling move consists of removing two pebbles from one vertex and then placing one pebble at an adjacent vertex. If a distribution δ of pebbles lets us move at least one pebble to each vertex by applying pebbling moves repeatedly(if necessary), then δ is called a pebbling of G. The optimal pebbling number f′(G) of G is the minimum number of pebbles used in a pebbling of G. In this paper, we improve the known upper bound for the optimal pebbling number of the hypercubes Q _n . Mainly, we prove for large n, $f'(Q_{n})=O(n^{3/2}(\frac {4}{3})^{n})$ by a probabilistic argument.     

An upper bound on the double Roman domination number

A double Roman dominating function (DRDF) on a graph \(G=(V,E)\) is a function \(f : V \rightarrow \{0, 1, 2, 3\}\) having the property that if \(f(v) = 0\), then vertex v must have at least two neighbors assigned 2 under f or one neighbor w with \(f(w)=3\), and if \(f(v)=1\), then vertex v must have at least one neighbor w with \(f(w)\ge 2\). The weight of a DRDF f is the value \(f(V) = \sum _{u \in V}f(u)\). The double Roman domination number \(\gamma _{dR}(G)\) of a graph G is the minimum weight of a DRDF on G. Beeler et al. (Discrete Appl Math 211:23–29, 2016) observed that every connected graph G having minimum degree at least two satisfies the inequality \(\gamma _{dR}(G)\le \frac{6n}{5}\) and posed the question whether this bound can be improved. In this paper, we settle the question and prove that for any connected graph G of order n with minimum degree at least two, \(\gamma _{dR}(G)\le \frac{8n}{7}\).     

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.     

On computing a minimum secure dominating set in block graphs

In a graph \(G=(V,E)\), a set \(D \subseteq V\) is said to be a dominating set of G if for every vertex \(u\in V{\setminus }D\), there exists a vertex \(v\in D\) such that \(uv\in E\). A secure dominating set of the graph G is a dominating set D of G such that for every \(u\in V{\setminus }D\), there exists a vertex \(v\in D\) such that \(uv\in E\) and \((D{\setminus }\{v\})\cup \{u\}\) is a dominating set of G. Given a graph G and a positive integer k, the secure domination problem is to decide whether G has a secure dominating set of cardinality at most k. The secure domination problem has been shown to be NP-complete for chordal graphs via split graphs and for bipartite graphs. In Liu et al. (in: Proceedings of 27th workshop on combinatorial mathematics and computation theory, 2010), it is asked to find a polynomial time algorithm for computing a minimum secure dominating set in a block graph. In this paper, we answer this by presenting a linear time algorithm to compute a minimum secure dominating set in block graphs. We then strengthen the known NP-completeness of the secure domination problem by showing that the secure domination problem is NP-complete for undirected path graphs and chordal bipartite graphs.     

Distance domination in graphs with given minimum and maximum degree

For an integer \(k \ge 1\), a distance k-dominating set of a connected graph G is a set S of vertices of G such that every vertex of V(G) is at distance at most k from some vertex of S. The distance k-domination number \(\gamma _k(G)\) of G is the minimum cardinality of a distance k-dominating set of G. In this paper, we establish an upper bound on the distance k-domination number of a graph in terms of its order, minimum degree and maximum degree. We prove that for \(k \ge 2\), if G is a connected graph with minimum degree \(\delta \ge 2\) and maximum degree \(\Delta \) and of order \(n \ge \Delta + k - 1\), then \(\gamma _k(G) \le \frac{n + \delta - \Delta }{\delta + k - 1}\). This result improves existing known results.     

Planar graphs without chordal 5-cycles are 2-good

Let G be a connected graph with \(n\ge 2\) vertices. Suppose that a fire breaks out at a vertex v of G. A firefighter starts to protect vertices. At each step, the firefighter protects two vertices not yet on fire. At the end of each step, the fire spreads to all the unprotected vertices that have a neighbour on fire. Let sn\(_2(v)\) denote the maximum number of vertices in G that the firefighter can save when a fire breaks out at vertex v. The 2-surviving rate \(\rho _2(G)\) of G is defined to be the real number \(\frac{1}{n^2} \sum _{v\in V(G)} \mathrm{sn}_2(v)\). Then it is obvious that \(0<\rho _2(G)<1\). The graph G is called 2-good if there is a constant \(c>0\) such that \(\rho _2(G)>c\). In this paper, we prove that every planar graph with \(n\ge 2\) vertices and without chordal 5-cycles is 2-good.     

Improved floor-planning of graphs via adjacency-preserving transformations

Let G=(V,E) and G′=(V′,E′) be two graphs, an adjacency-preserving transformation from G to G′ is a one-to-many and onto mapping from V to V′ satisfying the following: (1) Each vertex v∈V in G is mapped to a non-empty subset \(\mathcal{A}(v)\subset V'\) in G′. The subgraph induced by \(\mathcal{A}(v)\) is a connected subgraph of G′; (2) if u≠v∈V, then \(\mathcal{A}(u)\cap\mathcal{A}(v)=\emptyset\); and (3) two vertices u and v are adjacent to each other in G if and only if subgraphs induced by \(\mathcal{A}(u)\) and \(\mathcal{A}(v)\) are connected in G′.In this paper, we study adjacency-preserving transformations from plane triangulations to irreducible triangulations (which are internally triangulated, with four exterior vertices and no separating triangles). As one shall see, our transformations not only preserve adjacency well, but also preserve the endowed realizers of plane triangulations well in the endowed transversal structures of the image irreducible triangulations, which may be desirable in some applications.We then present such an application in floor-planning of plane graphs. The expected grid size of the floor-plan of our linear time algorithm is improved to \((\frac{5n}{8}+O(1))\times (\frac{23n}{24}+O(1))\), though the worst case grid size bound of the algorithm remains \(\lfloor\frac{2n+1}{3}\rfloor\times(n-1)\), which is the same as the algorithm presented in Liao et al. (J. Algorithms 48:441–451, 2003).     

A note on domination and total domination in prisms

Recently, Azarija et al. (Electron J Combin:1.19, 2017) considered the prism \(G \mathop {\square }K_2\) of a graph G and showed that \(\gamma _t(G \mathop {\square }K_2) = 2\gamma (G)\) if G is bipartite, where \(\gamma _t(G)\) and \(\gamma (G)\) are the total domination number and the domination number of G. In this note, we give a simple proof and observe that there are similar results for other pairs of parameters. We also answer a question from that paper and show that for all graphs \(\gamma _t(G \mathop {\square }K_2) \ge \frac{4}{3}\gamma (G)\), and this bound is tight.     

On the b-coloring of tight graphs

A coloring c of a graph \(G=(V,E)\) is a b -coloring if for every color i there is a vertex, say w(i), of color i whose neighborhood intersects every other color class. The vertex w(i) is called a b-dominating vertex of color i. The b -chromatic number of a graph G, denoted by b(G), is the largest integer k such that G admits a b-coloring with k colors. Let m(G) be the largest integer m such that G has at least m vertices of degree at least \(m-1\). A graph G is tight if it has exactly m(G) vertices of degree \(m(G)-1\), and any other vertex has degree at most \(m(G)-2\). In this paper, we show that the b-chromatic number of tight graphs with girth at least 8 is at least \(m(G)-1\) and characterize the graphs G such that \(b(G)=m(G)\). Lin and Chang (2013) conjectured that the b-chromatic number of any graph in \(\mathcal {B}_{m}\) is m or \(m-1\) where \(\mathcal {B}_{m}\) is the class of tight bipartite graphs \((D,D{^\prime })\) of girth 6 such that D is the set of vertices of degree \(m-1\). We verify the conjecture of Lin and Chang for some subclass of \(\mathcal {B}_{m}\), and we give a lower bound for any graph in \(\mathcal {B}_{m}\).     

A simpler PTAS for connected <Emphasis Type="Italic">k</Emphasis>-path vertex cover in homogeneous wireless sensor network

Because of its application in the field of security in wireless sensor networks, k-path vertex cover (\(\hbox {VCP}_k\)) has received a lot of attention in recent years. Given a graph \(G=(V,E)\), a vertex set \(C\subseteq V\) is a k-path vertex cover (\(\hbox {VCP}_k\)) of G if every path on k vertices has at least one vertex in C, and C is a connected k-path vertex cover of G (\(\hbox {CVCP}_k\)) if furthermore the subgraph of G induced by C is connected. A homogeneous wireless sensor network can be modeled as a unit disk graph. This paper presents a new PTAS for \(\hbox {MinCVCP}_k\) on unit disk graphs. Compared with previous PTAS given by Liu et al., our method not only simplifies the algorithm and reduces the time-complexity, but also simplifies the analysis by a large amount.     

Paired-domination number of claw-free odd-regular graphs

A paired-dominating set of a graph G is a dominating set of vertices whose induced subgraph has a perfect matching, while the paired-domination number is the minimum cardinality of a paired-dominating set in the graph, denoted by \(\gamma _{pr}(G)\). Let G be a connected \(\{K_{1,3}, K_{4}-e\}\)-free cubic graph of order n. We show that \(\gamma _{pr}(G)\le \frac{10n+6}{27}\) if G is \(C_{4}\)-free and that \(\gamma _{pr}(G)\le \frac{n}{3}+\frac{n+6}{9(\lceil \frac{3}{4}(g_o+1)\rceil +1)}\) if G is \(\{C_{4}, C_{6}, C_{10}, \ldots , C_{2g_o}\}\)-free for an odd integer \(g_o\ge 3\); the extremal graphs are characterized; we also show that if G is a 2 -connected, \(\gamma _{pr}(G) = \frac{n}{3} \). Furthermore, if G is a connected \((2k+1)\)-regular \(\{K_{1,3}, K_4-e\}\)-free graph of order n, then \(\gamma _{pr}(G)\le \frac{n}{k+1} \), with equality if and only if \(G=L(F)\), where \(F\cong K_{1, 2k+2}\), or k is even and \(F\cong K_{k+1,k+2}\).     

Scheduling with interjob communication on parallel processors

Consider a scheduling problem in which a set of tasks needs to be scheduled on m parallel processors. Each task \(T_i\) consists of a set of jobs with interjob communication demands, represented by a weighted, undirected graph \(G_i\). The processors are assumed to be interconnected by a shared communication channel, which can be used by jobs to communicate among each other while being processed in parallel. In each time step, the scheduler assigns jobs to the processors and allows any processed job to use a certain capacity of the channel in order to satisfy (parts of) its communication demands to adjacent jobs processed in the same step. The goal is to find a schedule with minimum length in which the communication demands of all jobs are satisfied. We show that this problem is NP-hard in the strong sense even if the number of processors is constant and the underlying graph is a single path or a forest with arbitrary constant maximum degree. Consequently, we design and analyze approximation algorithms with asymptotic approximation ratio \(\min \{1.8, 1.5 \frac{m}{m-1}\}+1\) if the underlying graph G, the union of the \(G_i\), is a forest. For general graphs it is \(\min \left\{ 1.8, \frac{1.5m}{m-1}\right\} \cdot \left( \text {arb}(G) + \frac{5}{3}\right) \), where \(\text {arb}(G)\) denotes the arboricity of G.     

Neighbor product distinguishing total colorings

A total-[k]-coloring of a graph G is a mapping \(\phi : V (G) \cup E(G)\rightarrow \{1, 2, \ldots , k\}\) such that any two adjacent elements in \(V (G) \cup E(G)\) receive different colors. Let f(v) denote the product of the color of a vertex v and the colors of all edges incident to v. A total-[k]-neighbor product distinguishing-coloring of G is a total-[k]-coloring of G such that \(f(u)\ne f(v)\), where \(uv\in E(G)\). By \(\chi ^{\prime \prime }_{\prod }(G)\), we denote the smallest value k in such a coloring of G. We conjecture that \(\chi _{\prod }^{\prime \prime }(G)\le \Delta (G)+3\) for any simple graph with maximum degree \(\Delta (G)\). In this paper, we prove that the conjecture holds for complete graphs, cycles, trees, bipartite graphs and subcubic graphs. Furthermore, we show that if G is a \(K_4\)-minor free graph with \(\Delta (G)\ge 4\), then \(\chi _{\prod }^{\prime \prime }(G)\le \Delta (G)+2\).     

List 2-distance $$\varDelta +3$$-coloring of planar graphs without 4,5-cycles

Let \(\chi _2(G)\) and \(\chi _2^l(G)\) be the 2-distance chromatic number and list 2-distance chromatic number of a graph G, respectively. Wegner conjectured that for each planar graph G with maximum degree \(\varDelta \) at least 4, \(\chi _2(G)\le \varDelta +5\) if \(4\le \varDelta \le 7\), and \(\chi _2(G)\le \lfloor \frac{3\varDelta }{2}\rfloor +1\) if \(\varDelta \ge 8\). Let G be a planar graph without 4,5-cycles. We show that if \(\varDelta \ge 26\), then \(\chi _2^l(G)\le \varDelta +3\). There exist planar graphs G with girth \(g(G)=6\) such that \(\chi _2^l(G)=\varDelta +2\) for arbitrarily large \(\varDelta \). In addition, we also discuss the list L(2, 1)-labeling number of G, and prove that \(\lambda _l(G)\le \varDelta +8\) for \(\varDelta \ge 27\).     

Algorithm complexity of neighborhood total domination and $$(\rho ,\gamma _{nt})$$-graphs

A neighborhood total dominating set, abbreviated for NTD-set D, is a vertex set of G such that D is a dominating set with an extra property: the subgraph induced by the open neighborhood of D has no isolated vertex. The neighborhood total domination number, denoted by \(\gamma _{nt}(G)\), is the minimum cardinality of a NTD-set in G. In this paper, we prove that NTD problem is NP-complete for bipartite graphs and split graphs. Then we give a linear-time algorithm to determine \(\gamma _{nt}(T)\) for a given tree T. Finally, we characterize a constructive property of \((\gamma _{nt},2\gamma )\)-trees and provide a constructive characterization for \((\rho ,\gamma _{nt})\)-graphs, where \(\gamma \) and \(\rho \) are domination number and packing number for the given graph, respectively.     

Coupon coloring of some special graphs

Let G be a graph without isolated vertices. A k-coupon coloring of G is a k-coloring of G such that the neighborhood of every vertex of G contains vertices of all colors from \([k] =\{1, 2, \ldots , k\}\), which was recently introduced by Chen, Kim, Tait and Verstraete. The coupon coloring number \(\chi _c(G)\) of G is the maximum k for which a k-coupon coloring exists. In this paper, we mainly study the coupon coloring of some special classes of graphs. We determine the coupon coloring numbers of complete graphs, complete k-partite graphs, wheels, cycles, unicyclic graphs, bicyclic graphs and generalised \(\Theta \)-graphs.     

Near optimal algorithms for online weighted bipartite matching in adversary model

Bipartite matching is an important problem in graph theory. With the prosperity of electronic commerce, such as online auction and AdWords allocation, bipartite matching problem has been extensively studied under online circumstances. In this work, we study the online weighted bipartite matching problem in adversary model, that is, there is a weighted bipartite graph \(G=(L,R,E)\) and the left side L is known as input, while the vertices in R come one by one in an order arranged by the adversary. When each vertex in R comes, its adjacent edges and relative weights are revealed. The algorithm should irreversibly decide whether to match this vertex to an unmatched neighbor in L with the objective to maximize the total weight of the obtained matching. When the weights are unbounded, the best algorithm can only achieve a competitive ratio \(\varTheta \left( \frac{1}{n}\right) \), where n is the number of vertices coming online. Thus, we mainly deal with two variants: the bounded weight problem in which all weights are in the range \([\alpha , \beta ]\), and the normalized summation problem in which each vertex in one side has the same total weights. We design algorithms for both variants with competitive ratio \(\varTheta \left( \max \left\{ \frac{1}{\log \frac{\beta }{\alpha }},\frac{1}{n}\right\} \right) \) and \(\varTheta \left( \frac{1}{\log n}\right) \) respectively. Furthermore, we show these two competitive ratios are tight by providing the corresponding hardness results.     

On the coefficients of the independence polynomial of graphs

An independent set of a graph G is a set of pairwise non-adjacent vertices. Let \(i_k = i_k(G)\) be the number of independent sets of cardinality k of G. The independence polynomial \(I(G, x)=\sum _{k\geqslant 0}i_k(G)x^k\) defined first by Gutman and Harary has been the focus of considerable research recently, whereas \(i(G)=I(G, 1)\) is called the Merrifield–Simmons index of G. In this paper, we first proved that among all trees of order n,  the kth coefficient \(i_k\) is smallest when the tree is a path, and is largest for star. Moreover, the graph among all trees of order n with diameter at least d whose all coefficients of I(G, x) are largest is identified. Then we identify the graphs among the n-vertex unicyclic graphs (resp. n-vertex connected graphs with clique number \(\omega \)) which simultaneously minimize all coefficients of I(G, x), whereas the opposite problems of simultaneously maximizing all coefficients of I(G, x) among these two classes of graphs are also solved respectively. At last we characterize the graph among all the n-vertex connected graph with chromatic number \(\chi \) (resp. vertex connectivity \(\kappa \)) which simultaneously minimize all coefficients of I(G, x). Our results may deduce some known results on Merrifield–Simmons index of graphs.