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.     

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.     

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

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}\).     

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

Minimum 2-distance coloring of planar graphs and channel assignment

A 2-distance k-coloring of a graph G is a proper k-coloring such that any two vertices at distance two get different colors. \(\chi _{2}(G)\)=min{k|G has a 2-distance k-coloring}. Wegner conjectured that for each planar graph G with maximum degree \(\Delta \), \(\chi _2(G) \le 7\) if \(\Delta \le 3\), \(\chi _2(G) \le \Delta +5\) if \(4\le \Delta \le 7\) and \(\chi _2(G) \le \lfloor \frac{3\Delta }{2}\rfloor +1\) if \(\Delta \ge 8\). In this paper, we prove that: (1) If G is a planar graph with maximum degree \(\Delta \le 5\), then \(\chi _{2}(G)\le 20\); (2) If G is a planar graph with maximum degree \(\Delta \ge 6\), then \(\chi _{2}(G)\le 5\Delta -7\).     

Equitable vertex arboricity of 5-degenerate graphs

Wu et al. (Discret Math 313:2696–2701, 2013) conjectured that the vertex set of any simple graph G can be equitably partitioned into m subsets so that each subset induces a forest, where \(\Delta (G)\) is the maximum degree of G and m is an integer with \(m\ge \lceil \frac{\Delta (G)+1}{2}\rceil \). This conjecture is verified for 5-degenerate graphs in this paper.     

Bounding the total domination subdivision number of a graph in terms of its order

The total domination subdivision number \(\mathrm{sd}_{\gamma _{t}}(G)\) of a graph 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 \(\mathrm{sd}_{\gamma_{t}}(G)\leq \lfloor\frac{2n}{3}\rfloor\) for any simple connected graph G of order n≥3 other than K ₄. We also determine all simple connected graphs G with \(\mathrm{sd}_{\gamma_{t}}(G)=\lfloor\frac{2n}{3}\rfloor\).     

Minimum choosability of planar graphs

The problem of list coloring of graphs appears in practical problems concerning channel or frequency assignment. In this paper, we study the minimum number of choosability of planar graphs. A graph G is edge-k-choosable if whenever every edge x is assigned with a list of at least k colors, L(x)), there exists an edge coloring \(\phi \) such that \(\phi (x) \in L(x)\). Similarly, A graph G is toal-k-choosable if when every element (edge or vertex) x is assigned with a list of at least k colors, L(x), there exists an total coloring \(\phi \) such that \(\phi (x) \in L(x)\). We proved \(\chi '_{l}(G)=\Delta \) and \(\chi ''_{l}(G)=\Delta +1\) for a planar graph G with maximum degree \(\Delta \ge 8\) and without chordal 6-cycles, where the list edge chromatic number \(\chi '_{l}(G)\) of G is the smallest integer k such that G is edge-k-choosable and the list total chromatic number \(\chi ''_{l}(G)\) of G is the smallest integer k such that G is total-k-choosable.     

Neighbor-sum-distinguishing edge choosability of subcubic graphs

A graph G is said to be neighbor-sum-distinguishing edge k-choose if, for every list L of colors such that L(e) is a set of k positive real numbers for every edge e, there exists a proper edge coloring which assigns to each edge a color from its list so that for each pair of adjacent vertices u and v the sum of colors taken on the edges incident to u is different from the sum of colors taken on the edges incident to v. Let \(\mathrm{ch}^{\prime }_{\sum ^p}(G)\) denote the smallest integer k such that G is neighbor-sum-distinguishing edge k-choose. In this paper, we prove that if G is a subcubic graph with the maximum average degree mad(G), then (1) \(\mathrm{ch}^{\prime }_{\sum ^p}(G)\le 7\); (2) \(\mathrm{ch}^{\prime }_{\sum ^p}(G)\le 6\) if \(\hbox {mad}(G)<\frac{36}{13}\); (3) \(\mathrm{ch}^{\prime }_{\sum ^p}(G)\le 5\) if \(\hbox {mad}(G)<\frac{5}{2}\).     

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}\).     

Upper bounds of proper connection number of graphs

A total weighting of a graph G is a mapping \(\phi \) that assigns a weight to each vertex and each edge of G. The vertex-sum of \(v \in V(G)\) with respect to \(\phi \) is \(S_{\phi }(v)=\sum _{e\in E(v)}\phi (e)+\phi (v)\). A total weighting is proper if adjacent vertices have distinct vertex-sums. A graph \(G=(V,E)\) is called \((k,k')\)-choosable if the following is true: If each vertex x is assigned a set L(x) of k real numbers, and each edge e is assigned a set L(e) of \(k'\) real numbers, then there is a proper total weighting \(\phi \) with \(\phi (y)\in L(y)\) for any \(y \in V \cup E\). In this paper, we prove that for any graph \(G\ne K_1\), the Mycielski graph of G is (1,4)-choosable. Moreover, we give some sufficient conditions for the Mycielski graph of G to be (1,3)-choosable. In particular, our result implies that if G is a complete bipartite graph, a complete graph, a tree, a subcubic graph, a fan, a wheel, a Halin graph, or a grid, then the Mycielski graph of G is (1,3)-choosable.