Pebbling in powers of paths Alcón, Liliana; Hurlbert, Glenn
Discrete mathematics,
20/May , Volume:
346, Issue:
5
Journal Article
Peer reviewed
The t-fold pebbling number, πt(G), of a graph G is defined to be the minimum number m so that, from any given configuration of m pebbles on the vertices of G, it is possible to place at least t ...pebbles on any specified vertex via pebbling moves. It has been conjectured that the pebbling numbers of pyramid-free chordal graphs can be calculated in polynomial time.
The kth power G(k) of the graph G is obtained from G by adding an edge between any two vertices of distance at most k from each other. The kth power of the path Pn on n vertices is an important class of pyramid-free chordal graphs, and is a stepping stone to the more general class of k-paths and the still more general class of interval graphs. Pachter, Snevily, and Voxman (1995) calculated π(Pn(2)), Kim (2004) calculated π(Pn(3)), and Kim and Kim (2010) calculated π(Pn(4)). In this paper we calculate πt(Pn(k)) for all n, k, and t.
For a function D:V(G)→N, the D-pebbling number, π(G,D), of a graph G is defined to be the minimum number m so that, from any given configuration of m pebbles on the vertices of G, it is possible to place at least D(v) pebbles on each vertex v via pebbling moves. It has been conjectured that π(G,D)≤π|D|(G) for all G and D. We make the stronger conjecture that every G and D satisfies π(G,D)≤π|D|(G)−(s(D)−1), where s(D) counts the number of vertices v with D(v)>0. We prove that trees and Pn(k), for all n and k, satisfy the stronger conjecture.
The pebbling exponenteπ(G) of a graph G was defined by Pachter et al., to be the minimum k for which π(G(k))=n(G(k)). Of course, eπ(G)≤diam(G), and Czygrinow, Hurlbert, Kierstead, and Trotter (2002) proved that almost all graphs G have eπ(G)=1. Lourdusamy and Mathivanan (2015) proved several results on πt(Cn2), and Hurlbert (2017) proved an asymptotically tight formula for eπ(Cn). Our formula for πt(Pn(k)) allows us to compute eπ(Pn) within additively narrow bounds.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
We analyze the relation between three parameters of a chordal graph G: the number of non-separating cliques nsc(G), the asteroidal number an(G) and the leafage l(G). We show that an(G) is equal to ...the maximum value of nsc(H) over all connected induced subgraphs H of G. As a corollary, we prove that if G has no separating simplicial cliques then an(G)=l(G).
A graph G is minimal k-asteroidal if an(G)=k and an(H)<k for every proper connected induced subgraph H of G. The family of minimal k-asteroidal chordal graphs is unknown for every k>3; for k=3 it is the family described by Lekerkerker and Boland to characterize interval graphs. We prove that, for every minimal k-asteroidal chordal graph, all the above parameters are equal to k. In addition, we characterize the split graphs that are minimal k-asteroidal and obtain all the minimal 4-asteroidal split graphs. Finally, we applied our results on asteroidal sets to describe the clutters with k edges that are minor-minimal in the sense that every minor has less than k edges.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
A
k
-tree is either a complete graph on
k
vertices or a graph that contains a vertex whose neighborhood induces a complete graph on
k
vertices and whose removal results in a
k
-tree. If the ...comparability graph of a poset
P
is a
k
-tree, we say that
P
is a
k
-tree poset. In the present work, we study and characterize by forbidden subposets the
k
-tree posets that admit a containment model mapping vertices into paths of a tree (
CPT
k
-tree posets). Furthermore, we characterize the dually-
CPT
and strong-
CPT
k
-tree posets and their comparability graphs. The characterizations lead to efficient recognition algorithms for the respective classes.
Full text
Available for:
EMUNI, FIS, FZAB, GEOZS, GIS, IJS, IMTLJ, KILJ, KISLJ, MFDPS, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, SBMB, SBNM, UKNU, UL, UM, UPUK, VKSCE, ZAGLJ
A graph is clique–Helly if every family of pairwise intersecting (maximal) cliques has non-empty total intersection. Dourado, Protti and Szwarcfiter conjectured that every clique–Helly graph contains ...a vertex whose removal maintains it as a clique–Helly graph. We present here two infinite families of counterexamples to this conjecture.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
A Note on Path Domination Alcón, Liliana
Discussiones Mathematicae. Graph Theory,
11/2016, Volume:
36, Issue:
4
Journal Article
Peer reviewed
Open access
We study domination between different types of walks connecting two non-adjacent vertices u and v of a graph (shortest paths, induced paths, paths, tolled walks). We succeeded in characterizing those ...graphs in which every uv-walk of one particular kind dominates every uv-walk of other specific kind. We thereby obtained new characterizations of standard graph classes like chordal, interval and superfragile graphs.
Full text
Available for:
IZUM, KILJ, NUK, PILJ, PNG, SAZU, UL, UM, UPUK
In this paper, motivated by the questions posed by Spinrad in Spinrad (2003) and Golumbic and Trenk (2004), we investigate those posets that admit a containment model mapping vertices into paths of a ...tree and their comparability graphs, named CPT posets and CPT graphs, respectively. We present a necessary condition to be CPT and prove it is not sufficient. We provide further examples of CPT posets P whose dual Pd is non CPT. Thus, we introduce the notion of dually-CPT and strong-CPT posets. We demonstrate that, unlike what happens with posets admitting a containment model using interval of the line, the dimension and the interval dimension of CPT posets is unbounded. On the other hand, we find that the dimension of a CPT poset is at most the number of leaves of the tree used in the containment model. We give a characterization of CPT ( also dually-CPT and strong-CPT) split posets by a family of forbidden subposets. We prove that every tree is strong-CPT.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Full text
Available for:
EMUNI, FIS, FZAB, GEOZS, GIS, IJS, IMTLJ, KILJ, KISLJ, MFDPS, NLZOH, NUK, OBVAL, OILJ, PNG, SAZU, SBCE, SBJE, SBMB, SBNM, UKNU, UL, UM, UPUK, VKSCE, ZAGLJ
9.
Pebbling in semi-2-trees Alcón, Liliana; Gutierrez, Marisa; Hurlbert, Glenn
Discrete mathematics,
July 2017, 2017-07-00, Volume:
340, Issue:
7
Journal Article
Peer reviewed
Open access
Graph pebbling is a network model for transporting discrete resources that are consumed in transit. Deciding whether a given configuration on a particular graph can reach a specified target is ...NP-complete, even for diameter two graphs, and deciding whether the pebbling number has a prescribed upper bound is Π2P-complete. Recently we proved that the pebbling number of a split graph can be computed in polynomial time. This paper advances the program of finding other polynomial classes, moving away from the large tree width, small diameter case (such as split graphs) to small tree width, large diameter, continuing an investigation on the important subfamily of chordal graphs called k-trees. In particular, we provide a formula, that can be calculated in polynomial time, for the pebbling number of any semi-2-tree, falling shy of the result for the full class of 2-trees.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
PDF
