一些乘积图的覆盖数

在图上进行小石块的移动的步骤为从一个点上取走两个小石块,并在它的某个邻点上放一个小石块.显然存在某个自然数,当图的所有点上的小石块的总数大于或等于它时,无论小石块在图上是如何初始分布的,都可以经过一系列的上述步骤,使得每个点上都至少有一个小石块.对一个图而言,满足此条件的最小的自然数即为此图的覆盖数.解决了字典乘积图和一些强乘积图的覆盖数问题,并给出了任意一个图的关键点与直径的两个端点之间的关系.

Cover pebbling number of some product graphs

A pebbling move on a graph G consists of taking two pebbles off from a vertex and placing one pebble on an adjacent vertex. The cover pebbling number of a graph, γ(G), is the minimum 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. The cover pebbling number for lexicographic product graphs and some strong product graphs were determined. The relationship between key vertices and ends of diameters for an arbitrary graph with a fixed diameter was obtained.