Improved pebbling bounds

Consider a configuration of pebbles distributed on the vertices of a connected graph of order n. A pebbling step consists of removing two pebbles from a given vertex and placing one pebble on an adjacent vertex. A distribution of pebbles on a graph is called solvable if it is possible to place a pebble on any given vertex using a sequence of pebbling steps. The pebbling number of a graph, denoted f(G), is the minimal number of pebbles such that every configuration of f(G) pebbles on G is solvable. We derive several general upper bounds on the pebbling number, improving previous results.     

t-Pebbling and Extensions

Graph pebbling is the study of moving discrete pebbles from certain initial distributions on the vertices of a graph to various target distributions via pebbling moves. A pebbling move removes two pebbles from a vertex and places one pebble on one of its neighbors (losing the other as a toll). For t ≥ 1 the t-pebbling number of a graph is the minimum number of pebbles necessary so that from any initial distribution of them it is possible to move t pebbles to any vertex. We provide the best possible upper bound on the t-pebbling number of a diameter two graph, proving a conjecture of Curtis et al., in the process. We also give a linear time (in the number of edges) algorithm to t-pebble such graphs, as well as a quartic time (in the number of vertices) algorithm to compute the pebbling number of such graphs, improving the best known result of Bekmetjev and Cusack. Furthermore, we show that, for complete graphs, cycles, trees, and cubes, we can allow the target to be any distribution of t pebbles without increasing the corresponding t-pebbling numbers; we conjecture that this behavior holds for all graphs. Finally, we explore fractional and optimal fractional versions of pebbling, proving the fractional pebbling number conjecture of Hurlbert and using linear optimization to reveal results on the optimal fractional pebbling number of vertex-transitive graphs.     

Graham's pebbling conjecture on products of cycles

Chung defined a pebbling move on a graph G to be the removal of two pebbles from one vertex and the addition of one pebble to an adjacent vertex. The pebbling number of a connected graph is the smallest number f(G) such that any distribution of f(G) pebbles on G allows one pebble to be moved to any specified, but arbitrary vertex by a sequence of pebbling moves. Graham conjectured that for any connected graphs G and H, f(G×H)≤ f(G)f(H). We prove Graham's conjecture when G is a cycle for a variety of graphs H, including all cycles. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 141–154, 2003     

Signed k-independence in graphs

Let k ≥ 2 be an integer. A function f: V(G) → {?1, 1} defined on the vertex set V(G) of a graph G is a signed k-independence function if the sum of its function values over any closed neighborhood is at most k ? 1. That is, Σ _x∈N[v] f(x) ≤ k ? 1 for every v ∈ V(G), where N[v] consists of v and every vertex adjacent to v. The weight of a signed k-independence function f is w(f) = Σ _v∈V(G) f(v). The maximum weight w(f), taken over all signed k-independence functions f on G, is the signed k-independence number α _s ^k (G) of G. In this work, we mainly present upper bounds on α _s ^k (G), as for example α _s ^k (G) ≤ n ? 2?(Δ(G) + 2 ? k)/2?, and we prove the Nordhaus-Gaddum type inequality $\alpha _S^k \left( G \right) + \alpha _S^k \left( {\bar G} \right) \leqslant n + 2k - 3$ , where n is the order, Δ(G) the maximum degree and $\bar G$ the complement of the graph G. Some of our results imply well-known bounds on the signed 2-independence number.     

Maximum pebbling number of graphs of diameter three

Given a configuration of pebbles on the vertices of a graph G, a pebbling move consists of taking two pebbles off some vertex v and putting one of them back on a vertex adjacent to v. A graph is called pebbleable if for each vertex v there is a sequence of pebbling moves that would place at least one pebble on v. The pebbling number of a graph G is the smallest integer m such that G is pebbleable for every configuration of m pebbles on G. We prove that the pebbling number of a graph of diameter 3 on n vertices is no more than (3/2)n + O(1), and, by explicit construction, that the bound is sharp. © 2006 Wiley Periodicals, Inc. J Graph Theory     

Threshold and complexity results for the cover pebbling game

Given a configuration of pebbles on the vertices of a graph, a pebbling move is defined by removing two pebbles from some vertex and placing one pebble on an adjacent vertex. The cover pebbling number of a graph, γ(G), is the smallest number of pebbles such that through a sequence of pebbling moves, a pebble can eventually be placed on every vertex simultaneously, no matter how the pebbles are initially distributed. We determine Bose-Einstein and Maxwell-Boltzmann cover pebbling thresholds for the complete graph. Also, we show that the cover pebbling decision problem is NP-complete.     

Graham’s pebbling conjecture on products of many cycles

A pebbling move on a connected graph G consists of removing two pebbles from some vertex and adding one pebble to an adjacent vertex. We define f_t(G) as the smallest number such that whenever f_t(G) pebbles are on G, we can move t pebbles to any specified, but arbitrary vertex. Graham conjectured that f₁(G×H)≤f₁(G)f₁(H) for any connected G and H. We define the α-pebbling number α(G) and prove that α(C_pj×?×C_p2×C_p1×G)≤α(C_pj)?α(C_p2)α(C_p1)α(G) when none of the cycles is C₅, and G satisfies one more criterion. We also apply this result with G=C₅×C₅ by showing that C₅×C₅ satisfies Chung’s two-pebbling property, and establishing bounds for f_t(C₅×C₅).     

On the Lucky Choice Number of Graphs

Suppose that G is a graph and ${f: V (G) \rightarrow \mathbb{N}}$ is a labeling of the vertices of G. Let S(v) denote the sum of labels over all neighbors of the vertex v in G. A labeling f of G is called lucky if ${S(u) \neq S(v),}$ for every pair of adjacent vertices u and v. Also, for each vertex ${v \in V(G),}$ let L(v) denote a list of natural numbers available at v. A list lucky labeling, is a lucky labeling f such that ${f(v) \in L(v),}$ for each ${v \in V(G).}$ A graph G is said to be lucky k-choosable if every k-list assignment of natural numbers to the vertices of G permits a list lucky labeling of G. The lucky choice number of G, η _l (G), is the minimum natural number k such that G is lucky k-choosable. In this paper, we prove that for every graph G with ${\Delta \geq 2, \eta_{l}(G) \leq \Delta^2-\Delta + 1,}$ where Δ denotes the maximum degree of G. Among other results we show that for every 3-list assignment to the vertices of a forest, there is a list lucky labeling which is a proper vertex coloring too.     

The 2-Pebbling Property and a Conjecture of Graham's

The pebbling number of a graph G, f(G), is the least m such that, however m pebbles are placed on the vertices of G, we can move a pebble to any vertex by a sequence of moves, each move taking two pebbles off one vertex and placing one on an adjacent vertex. It is conjectured that for all graphs G and H, f(G 2H)hf(G)f(H).¶Let C_m and C_n be cycles. We prove that f(C_m 2C_n)hf(C_m) f(C_n) for all but a finite number of possible cases. We also prove that f(G2T)hf(G) f(T) when G has the 2-pebbling property and T is any tree.     

Note on a conjecture of sierksma

LetS(q, d) be the maximal numberv such that, for every general position linear maph: Δ^(q?1)(d+1) →R ^d, there exist at leastv different collections {Δ ^t1, ..., Δ ^t _q} of disjoint faces of Δ(q?1)(d+1) with the property thatf(Δ ^t1) ∩ ... ∩f(Δ ^t _q) ≠ Ø. Sierksma's conjecture is thatS(q, d)=((q?1)!) ^d . The following lower bound (Theorem 1) is proved assuming thatq is a prime number: $$S(q,d) \geqslant \frac{1}{{(q - 1)!}}\left( {\frac{q}{2}} \right)^{{{((q - 1)(d + 1))} \mathord{\left/ {\vphantom {{((q - 1)(d + 1))} 2}} \right. \kern-\nulldelimiterspace} 2}} .$$ Using the same technique we obtain (Theorem 2) a lower bound for the number of different splittings of a “generic” necklace.     

Mean-Field Conditions for Percolation on Finite Graphs

Let {G _n } be a sequence of finite transitive graphs with vertex degree d = d(n) and |G _n | = n. Denote by p ^t (v, v) the return probability after t steps of the non-backtracking random walk on G _n . We show that if p ^t (v, v) has quasi-random properties, then critical bond-percolation on G _n behaves as it would on a random graph. More precisely, if $\mathop {\rm {lim\, sup\,}} \limits_{n} n^{1/3} \sum\limits_{t = 1}^{n^{1/3}} {t{\bf p}^t(v,v) < \infty ,}$ then the size of the largest component in p-bond-percolation with ${p =\frac{1+O(n^{-1/3})}{d-1}}Let {G _n } be a sequence of finite transitive graphs with vertex degree d = d(n) and |G _n | = n. Denote by p ^t (v, v) the return probability after t steps of the non-backtracking random walk on G _n . We show that if p ^t (v, v) has quasi-random properties, then critical bond-percolation on G _n behaves as it would on a random graph. More precisely, if

lim sup  n n1/3 ?t = 1n1/3 tpt(v,v) < ￥,\mathop {\rm {lim\, sup\,}} \limits_{n} n^{1/3} \sum\limits_{t = 1}^{n^{1/3}} {t{\bf p}^t(v,v) < \infty ,}      12. Graham’s pebbling conjecture on product of thorn graphs of complete graphs      Zhiping Wang  Zhongtuo Wang 《Discrete Mathematics》2009,309(10):3431-3435 The pebbling number of a graph G, f(G), is the least n such that, no matter how n pebbles are placed on the vertices of G, we can move a pebble to any vertex by a sequence of pebbling moves, each move taking two pebbles off one vertex and placing one on an adjacent vertex. Let p1,p2,…,pn be positive integers and G be such a graph, V(G)=n. The thorn graph of the graph G, with parameters p1,p2,…,pn, is obtained by attaching pi new vertices of degree 1 to the vertex ui of the graph G, i=1,2,…,n. Graham conjectured that for any connected graphs G and H, f(G×H)≤f(G)f(H). We show that Graham’s conjecture holds true for a thorn graph of the complete graph with every by a graph with the two-pebbling property. As a corollary, Graham’s conjecture holds when G and H are the thorn graphs of the complete graphs with every .      13. A special f-edge cover-coloring of multigraphs      Yongxun Xin  Guizhen Liu 《Journal of Applied Mathematics and Computing》2008,26(1-2):465-474 An edge cover-coloring of G is called a special (f,g)-edge cover-coloring, if each color appears at each vertex at least f(v) times and the number of multiple edges receive the same color is at most g(vw) for vw∈E(G). Let $\chi_{f_{g}}''$ denote the maximum positive integer k for which using k colors a special (f,g)-edge cover-coloring of G exists. The existence of $\chi_{f_{g}}''$ is discussed and the lower bound of $\chi_{f_{g}}''$ is obtained.      14. Fractional f-Edge Cover Chromatic Index of Graphs      Jinbo Li  Guizhen Liu  Guanghui Wang 《Graphs and Combinatorics》2014,30(3):687-698 Let G be a graph, and let f be an integer function on V with ${1\leq f(v)\leq d(v)}$ to each vertex ${\upsilon \in V}$ . An f-edge cover coloring is a coloring of edges of E(G) such that each color appears at each vertex ${\upsilon \in V(G)}$ at least f(υ) times. The maximum number of colors needed to f-edge cover color G is called the f-edge cover chromatic index of G and denoted by ${\chi^{'}_{fc}(G)}$ . It is well known that any simple graph G has the f-edge cover chromatic index equal to δ f (G) or δ f (G) ? 1, where ${\delta_{f}(G)=\,min\{\lfloor \frac{d(v)}{f(v)} \rfloor: v\in V(G)\}}$ . The fractional f-edge cover chromatic index of a graph G, denoted by ${\chi^{'}_{fcf}(G)}$ , is the fractional f-matching number of the edge f-edge cover hypergraph ${\mathcal{H}}$ of G whose vertices are the edges of G and whose hyperedges are the f-edge covers of G. In this paper, we give an exact formula of ${\chi^{'}_{fcf}(G)}$ for any graph G, that is, ${\chi^{'}_{fcf}(G)=\,min \{\min\limits_{v\in V(G)}d_{f}(v), \lambda_{f}(G)\}}$ , where ${\lambda_{f}(G)=\min\limits_{S} \frac{|C[S]|}{\lceil (\sum\limits_{v\in S}{f(v)})/2 \rceil}}$ and the minimum is taken over all nonempty subsets S of V(G) and C[S] is the set of edges that have at least one end in S.      15. Some properties onf-edge covered critical graphs      Jihui Wang  Jianfeng Hou  Guizhen Liu 《Journal of Applied Mathematics and Computing》2007,24(1-2):357-366 LetG(V, E) be a simple graph, and letf be an integer function onV with 1 ≤f(v) ≤d(v) to each vertexv ∈V. An f-edge cover-coloring of a graphG is a coloring of edge setE such that each color appears at each vertexv ∈V at leastf(v) times. Thef-edge cover chromatic index ofG, denoted by χ′ fc (G), is the maximum number of colors such that anf-edge cover-coloring ofG exists. Any simple graphG has anf-edge cover chromatic index equal to δf or δ f - 1, where $\delta _f = \mathop {\min }\limits_{\upsilon \in V} \{ \left\lfloor {\frac{{d(v)}}{{f(v)}}} \right\rfloor \} $ . LetG be a connected and not complete graph with χ′ fc (G)=δ f-1, if for eachu, v ∈V and e =uv ?E, we have ÷ fc (G + e) > ÷ fc (G), thenG is called anf-edge covered critical graph. In this paper, some properties onf-edge covered critical graph are discussed. It is proved that ifG is anf-edge covered critical graph, then for eachu, v ∈V and e =uv ?E there existsw ∈ {u, v } withd(w) ≤ δ f (f(w) + 1) - 2 such thatw is adjacent to at leastd(w) - δ f + 1 vertices which are all δ f -vertex inG.      16. On the Fourth Moment of Coefficients of Symmetric Square L-Function      Huixue LAO 《数学年刊B辑(英文版)》2012,33(6):877-888 Let f(z) be a holomorphic Hecke eigencuspform of weight k for the full modular group. Let ?? f (n) be the nth normalized Fourier coefficient of f(z). Suppose that L(sym2 f, s) is the symmetric square L-function associated with f(z), and $ \lambda _{sym^2 f} (n) $ (n) denotes the nth coefficient L(sym2 f, s). In this paper, it is proved that $$ \sum\limits_{n \leqslant x} {\lambda _{sym^2 f}^4 (n)} = xP2(\log x) + O(x^{\frac{{79}} {{81}} + \varepsilon } ), $$ , where P 2(t) is a polynomial in t of degree 2. Similarly, it is obtained that $$ \sum\limits_{n \leqslant x} {\lambda _f^4 (n^2 )} = x\tilde P2(\log x) + O(x^{\frac{{79}} {{81}} + \varepsilon } ), $$ , where $ \tilde P_2 (t) $ is a polynomial in t of degree 2.      17. New bounds for the broadcast domination number of a graph      Richard C. Brewster  Christina M. Mynhardt  Laura E. Teshima 《Central European Journal of Mathematics》2013,11(7):1334-1343 A dominating broadcast on a graph G = (V, E) is a function f: V → {0, 1, ..., diam G} such that f(v) ≤ e(v) (the eccentricity of v) for all v ∈ V and such that each vertex is within distance f(v) from a vertex v with f(v) > 0. The cost of a broadcast f is σ(f) = Σ v∈V f(v), and the broadcast number λ b (G) is the minimum cost of a dominating broadcast. A set X ? V(G) is said to be irredundant if each x ∈ X dominates a vertex y that is not dominated by any other vertex in X; possibly y = x. The irredundance number ir (G) is the cardinality of a smallest maximal irredundant set of G. We prove the bound λb(G) ≤ 3 ir(G)/2 for any graph G and show that equality is possible for all even values of ir (G). We also consider broadcast domination as an integer programming problem, the dual of which provides a lower bound for λb.      18. Roman Domination Dot-critical Graphs      Nader Jafari Rad  Lutz Volkmann 《Graphs and Combinatorics》2013,29(3):527-533 A Roman dominating function on a graph G is a function f : V(G) → {0, 1, 2} satisfying the condition that every vertex u for which f (u) = 0 is adjacent to at least one vertex v for which f (v) = 2. The weight of a Roman dominating function is the value ${f(V(G))=\sum_{u \in V(G)}f(u)}$ . The Roman domination number, γ R (G), of G is the minimum weight of a Roman dominating function on G. In this paper, we study graphs for which contracting any edge decreases the Roman domination number.      19. 多扇图的Pebbling数和Graham猜想          下载免费PDF全文 王艳秋  叶永升 《运筹与管理》2015,24(4):137-140 图G的pebbling数f(G)是最小的整数n,使得不论n个pebble如何放置在G的顶点上,总可以通过一系列的pebbling移动把1个pebble移到任意一个顶点上,其中一个pebbling移动是从一个顶点处移走两个pebble而把其中的一个移到与其相邻的一个顶点上。Graham猜想对于任意的连通图G和H有f(G×H)f(G)f(H)。多扇图Fn1,n2,…,nm是指阶为n1+n2+…+nm+1的联图P1∨(Pn1∪Pn2∪…∪Pnm)。本文首先给出了多扇图的pebbling数,然后证明了多扇图Fn1,n2,…,nm具有2-pebbling性质,最后论述了对于一个多扇图和一个具有2-pebbling性质的图的乘积来说,Graham猜想是成立的。作为一个推论,当G和H都是多扇图时,Graham猜想成立。      20. Degree Distance of Unicyclic Graphs with Given Matching Number      Lihua Feng  Weijun Liu  Aleksandar Ilić  Guihai Yu 《Graphs and Combinatorics》2013,29(3):449-462 Let G be a connected graph with vertex set V(G). The degree distance of G is defined as ${D'(G) = \sum_{\{u, v\}\subseteq V(G)} (d_G(u) + d_G (v))\, d(u,v)}$ , where d G (u) is the degree of vertex u, d(u, v) denotes the distance between u and v, and the summation goes over all pairs of vertices in G. In this paper, we characterize n-vertex unicyclic graphs with given matching number and minimal degree distance.

Graham’s pebbling conjecture on product of thorn graphs of complete graphs

The pebbling number of a graph G, f(G), is the least n such that, no matter how n pebbles are placed on the vertices of G, we can move a pebble to any vertex by a sequence of pebbling moves, each move taking two pebbles off one vertex and placing one on an adjacent vertex. Let p₁,p₂,…,p_n be positive integers and G be such a graph, V(G)=n. The thorn graph of the graph G, with parameters p₁,p₂,…,p_n, is obtained by attaching p_i new vertices of degree 1 to the vertex u_i of the graph G, i=1,2,…,n. Graham conjectured that for any connected graphs G and H, f(G×H)≤f(G)f(H). We show that Graham’s conjecture holds true for a thorn graph of the complete graph with every by a graph with the two-pebbling property. As a corollary, Graham’s conjecture holds when G and H are the thorn graphs of the complete graphs with every .     

A special f-edge cover-coloring of multigraphs

An edge cover-coloring of G is called a special (f,g)-edge cover-coloring, if each color appears at each vertex at least f(v) times and the number of multiple edges receive the same color is at most g(vw) for vw∈E(G). Let $\chi_{f_{g}}''$ denote the maximum positive integer k for which using k colors a special (f,g)-edge cover-coloring of G exists. The existence of $\chi_{f_{g}}''$ is discussed and the lower bound of $\chi_{f_{g}}''$ is obtained.     

Fractional f-Edge Cover Chromatic Index of Graphs

Let G be a graph, and let f be an integer function on V with ${1\leq f(v)\leq d(v)}$ to each vertex ${\upsilon \in V}$ . An f-edge cover coloring is a coloring of edges of E(G) such that each color appears at each vertex ${\upsilon \in V(G)}$ at least f(υ) times. The maximum number of colors needed to f-edge cover color G is called the f-edge cover chromatic index of G and denoted by ${\chi^{'}_{fc}(G)}$ . It is well known that any simple graph G has the f-edge cover chromatic index equal to δ _f (G) or δ _f (G) ? 1, where ${\delta_{f}(G)=\,min\{\lfloor \frac{d(v)}{f(v)} \rfloor: v\in V(G)\}}$ . The fractional f-edge cover chromatic index of a graph G, denoted by ${\chi^{'}_{fcf}(G)}$ , is the fractional f-matching number of the edge f-edge cover hypergraph ${\mathcal{H}}$ of G whose vertices are the edges of G and whose hyperedges are the f-edge covers of G. In this paper, we give an exact formula of ${\chi^{'}_{fcf}(G)}$ for any graph G, that is, ${\chi^{'}_{fcf}(G)=\,min \{\min\limits_{v\in V(G)}d_{f}(v), \lambda_{f}(G)\}}$ , where ${\lambda_{f}(G)=\min\limits_{S} \frac{|C[S]|}{\lceil (\sum\limits_{v\in S}{f(v)})/2 \rceil}}$ and the minimum is taken over all nonempty subsets S of V(G) and C[S] is the set of edges that have at least one end in S.     

Some properties onf-edge covered critical graphs

LetG(V, E) be a simple graph, and letf be an integer function onV with 1 ≤f(v) ≤d(v) to each vertexv ∈V. An f-edge cover-coloring of a graphG is a coloring of edge setE such that each color appears at each vertexv ∈V at leastf(v) times. Thef-edge cover chromatic index ofG, denoted by χ′ _fc (G), is the maximum number of colors such that anf-edge cover-coloring ofG exists. Any simple graphG has anf-edge cover chromatic index equal to δ_f or δ _f - 1, where $\delta _f = \mathop {\min }\limits_{\upsilon \in V} \{ \left\lfloor {\frac{{d(v)}}{{f(v)}}} \right\rfloor \} $ . LetG be a connected and not complete graph with χ′ _fc (G)=δ _f-1, if for eachu, v ∈V and e =uv ?E, we have ÷ _fc (G + e) > ÷ _fc (G), thenG is called anf-edge covered critical graph. In this paper, some properties onf-edge covered critical graph are discussed. It is proved that ifG is anf-edge covered critical graph, then for eachu, v ∈V and e =uv ?E there existsw ∈ {u, v } withd(w) ≤ δ _f (f(w) + 1) - 2 such thatw is adjacent to at leastd(w) - δ _f + 1 vertices which are all δ _f -vertex inG.     

On the Fourth Moment of Coefficients of Symmetric Square L-Function

Let f(z) be a holomorphic Hecke eigencuspform of weight k for the full modular group. Let ?? _f (n) be the nth normalized Fourier coefficient of f(z). Suppose that L(sym² f, s) is the symmetric square L-function associated with f(z), and $ \lambda _{sym^2 f} (n) $ (n) denotes the nth coefficient L(sym² f, s). In this paper, it is proved that $$ \sum\limits_{n \leqslant x} {\lambda _{sym^2 f}^4 (n)} = xP2(\log x) + O(x^{\frac{{79}} {{81}} + \varepsilon } ), $$ , where P ₂(t) is a polynomial in t of degree 2. Similarly, it is obtained that $$ \sum\limits_{n \leqslant x} {\lambda _f^4 (n^2 )} = x\tilde P2(\log x) + O(x^{\frac{{79}} {{81}} + \varepsilon } ), $$ , where $ \tilde P_2 (t) $ is a polynomial in t of degree 2.     

New bounds for the broadcast domination number of a graph

A dominating broadcast on a graph G = (V, E) is a function f: V → {0, 1, ..., diam G} such that f(v) ≤ e(v) (the eccentricity of v) for all v ∈ V and such that each vertex is within distance f(v) from a vertex v with f(v) > 0. The cost of a broadcast f is σ(f) = Σ _v∈V f(v), and the broadcast number λ _b (G) is the minimum cost of a dominating broadcast. A set X ? V(G) is said to be irredundant if each x ∈ X dominates a vertex y that is not dominated by any other vertex in X; possibly y = x. The irredundance number ir (G) is the cardinality of a smallest maximal irredundant set of G. We prove the bound λ_b(G) ≤ 3 ir(G)/2 for any graph G and show that equality is possible for all even values of ir (G). We also consider broadcast domination as an integer programming problem, the dual of which provides a lower bound for λ_b.     

Roman Domination Dot-critical Graphs

A Roman dominating function on a graph G is a function f : V(G) → {0, 1, 2} satisfying the condition that every vertex u for which f (u) = 0 is adjacent to at least one vertex v for which f (v) = 2. The weight of a Roman dominating function is the value ${f(V(G))=\sum_{u \in V(G)}f(u)}$ . The Roman domination number, γ _R (G), of G is the minimum weight of a Roman dominating function on G. In this paper, we study graphs for which contracting any edge decreases the Roman domination number.     

多扇图的Pebbling数和Graham猜想

图G的pebbling数f(G)是最小的整数n,使得不论n个pebble如何放置在G的顶点上,总可以通过一系列的pebbling移动把1个pebble移到任意一个顶点上,其中一个pebbling移动是从一个顶点处移走两个pebble而把其中的一个移到与其相邻的一个顶点上。Graham猜想对于任意的连通图G和H有f(G×H)f(G)f(H)。多扇图F_n1,n2,…,nm是指阶为n₁+n₂+…+n_m+1的联图P₁∨(P_n1∪P_n2∪…∪P_nm)。本文首先给出了多扇图的pebbling数,然后证明了多扇图F_n1,n2,…,nm具有2-pebbling性质,最后论述了对于一个多扇图和一个具有2-pebbling性质的图的乘积来说,Graham猜想是成立的。作为一个推论,当G和H都是多扇图时,Graham猜想成立。     

Degree Distance of Unicyclic Graphs with Given Matching Number

Let G be a connected graph with vertex set V(G). The degree distance of G is defined as ${D'(G) = \sum_{\{u, v\}\subseteq V(G)} (d_G(u) + d_G (v))\, d(u,v)}$ , where d _G (u) is the degree of vertex u, d(u, v) denotes the distance between u and v, and the summation goes over all pairs of vertices in G. In this paper, we characterize n-vertex unicyclic graphs with given matching number and minimal degree distance.