Given a distribution of pebbles on the vertices of a connected graph G, a pebbling move on G consists of taking two pebbles off one vertex and placing one on an adjacent vertex. Rubbling is a version of pebbling where an additional move is allowed. In this new move, one pebble each is removed at vertices u and w that are adjacent to a vertex v, and an extra pebble is added at vertex v. The rubbling number of G, denoted by ρ(G), is the smallest number m such that for every distribution of m pebbles on G and every vertex v, at least one pebble can be moved to v by a sequence of rubbling moves. The optimal rubbling number of G, denoted by ρopt(G), is the smallest number k such that for some distribution of k pebbles on G, one pebble can be moved to any vertex of G. In this paper, we determine ρ(G) for a non-complete bipartite graph G ∈ B(s, t) with <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\delta(G)\geq\lceil\frac{2s+1}{3}\rceil$</EquationSource> <EquationSource Format="MATHML"><math> <mi>δ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>≥</mo> <mo fence="false" stretchy="false">⌈</mo> <mfrac> <mrow> <mn>2</mn> <mi>s</mi> <mo>+</mo> <mn>1</mn> </mrow> <mn>3</mn> </mfrac> <mo fence="false" stretchy="false">⌉</mo> </math></EquationSource> </InlineEquation>, give an upper bound of ρ(G) for G ∈ B(s, t) with <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\delta(G)\geq\lceil\frac{s+1}{2}\rceil$</EquationSource> <EquationSource Format="MATHML"><math> <mi>δ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>≥</mo> <mo fence="false" stretchy="false">⌈</mo> <mfrac> <mrow> <mi>s</mi> <mo>+</mo> <mn>1</mn> </mrow> <mn>2</mn> </mfrac> <mo fence="false" stretchy="false">⌉</mo> </math></EquationSource> </InlineEquation>, and also obtain ρopt(G) for a non-complete bipartite graph G ∈ B(s, t) with <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\delta(G)\geq\lceil\frac{s+1}{2}\rceil$</EquationSource> <EquationSource Format="MATHML"><math> <mi>δ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>≥</mo> <mo fence="false" stretchy="false">⌈</mo> <mfrac> <mrow> <mi>s</mi> <mo>+</mo> <mn>1</mn> </mrow> <mn>2</mn> </mfrac> <mo fence="false" stretchy="false">⌉</mo> </math></EquationSource> </InlineEquation>, where B(s, t) is the set of all connected bipartite graphs with partite sets of size s and t (s ≥ t) and δ(G) is the minimum degree of G.

Rubbling and Optimal Rubbling of Dense Bipartite Graphs

期刊论文
发表日期：

2025年5月31日

查看全文

Ze-tu Gao,
Jian-hua Yin

摘要

Given a distribution of pebbles on the vertices of a connected graph G, a pebbling move on G consists of taking two pebbles off one vertex and placing one on an adjacent vertex. Rubbling is a version of pebbling where an additional move is allowed. In this new move, one pebble each is removed at vertices u and w that are adjacent to a vertex v, and an extra pebble is added at vertex v. The rubbling number of G, denoted by ρ(G), is the smallest number m such that for every distribution of m pebbles on G and every vertex v, at least one pebble can be moved to v by a sequence of rubbling moves. The optimal rubbling number of G, denoted by ρ_opt(G), is the smallest number k such that for some distribution of k pebbles on G, one pebble can be moved to any vertex of G. In this paper, we determine ρ(G) for a non-complete bipartite graph G ∈ B(s, t) with $\delta(G)\geq\lceil\frac{2s+1}{3}\rceil$ $δ (G) \geq ⌈ \frac{2 s + 1}{3} ⌉$ , give an upper bound of ρ(G) for G ∈ B(s, t) with $\delta(G)\geq\lceil\frac{s+1}{2}\rceil$ $δ (G) \geq ⌈ \frac{s + 1}{2} ⌉$ , and also obtain ρ_opt(G) for a non-complete bipartite graph G ∈ B(s, t) with $\delta(G)\geq\lceil\frac{s+1}{2}\rceil$ $δ (G) \geq ⌈ \frac{s + 1}{2} ⌉$ , where B(s, t) is the set of all connected bipartite graphs with partite sets of size s and t (s ≥ t) and δ(G) is the minimum degree of G.