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

星形图乘积的pebbling数

图 G的 pebbling数 f(G)是最小的整数 n,使得不论 n个 pebble如何放置在 G的顶点上 ,总可以通过一系列的 pebbling移动把一个 pebble移到任意一个顶点上 ,其中的 pebbling移动是从一个顶点上移走两个 pebble而把其中的一个移到与其相邻的一个顶点上 .设 K1,n为 n+1个顶点的星形图 .本文证明了 (n+2 )(m+2 )≥ f K1,n× K1,m)≥ (n+1) (m+1) +7,n>1,m>1.     

Graham’s pebbling conjecture on product of complete bipartite 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 moves, each move taking two pebbles off one vertex and placing one on an adjacent vertex. Graham conjectured that for any connected graphs G and H, f( G x H) ⩽ f( G) f( H). We show that Graham’s conjecture holds true of a complete bipartite graph by a graph with the two-pebbling property. As a corollary, Graham’s conjecture holds when G and H are complete bipartite graphs.     

Pebbling numbers of some graphs

Chung defined a pebbling move on a graphG as the removal of two pebbles from one vertex and the addition of one pebble to an adjacent vertex. The pebbling number of a connected graphG, f(G), is the leastn such that any distribution ofn pebbles onG allows one pebble to be moved to any specified but arbitrary vertex by a sequence of pebbling moves. Graham conjectured that for any connected graphsG andH, f(G xH) ≤ f(G)f(H). In the present paper the pebbling numbers of the product of two fan graphs and the product of two wheel graphs are computed. As a corollary, Graham’s conjecture holds whenG andH are fan graphs or wheel graphs.     

Vizing’s conjecture for chordal graphs

Vizing conjectured that γ(G□H)≥γ(G)γ(H) for every pair G,H of graphs, where “□” is the Cartesian product, and γ(G) is the domination number of the graph G. Denote by γⁱ(G) the maximum, over all independent sets I in G, of the minimal number of vertices needed to dominate I. We prove that γ(G□H)≥γⁱ(G)γ(H). Since for chordal graphs γⁱ=γ, this proves Vizing’s conjecture when G is chordal.     

On Seymour’s strengthening of Hadwiger’s conjecture for graphs with certain forbidden subgraphs

Let H be a set of graphs. A graph is called H-free if it does not contain a copy of a member of H as an induced subgraph. If H is a graph then G is called H-free if it is {H}-free. Plummer, Stiebitz, and Toft proved that, for every -free graph H on at most four vertices, every -free graph G has a collection of ⌈|V(G)|/2⌉ many pairwise adjacent vertices and edges (where a vertexvand an edgeeare adjacent if v is disjoint from the set V(e) of endvertices of e and adjacent to some vertex of V(e), and two edgeseandfare adjacent if V(e) and V(f) are disjoint and some vertex of V(e) is adjacent to some vertex of V(f)). Here we generalize this statement to -free graphs H on at most five vertices.     

Ohba’s conjecture for graphs with independence number five

Ohba has conjectured that if G is a k-chromatic graph with at most 2k+1 vertices, then the list chromatic number or choosability of G is equal to its chromatic number χ(G), which is k. It is known that this holds if G has independence number at most three. It is proved here that it holds if G has independence number at most five. In particular, and equivalently, it holds if G is a complete k-partite graph and each part has at most five vertices.     

Proof of a conjecture on connectivity of Kronecker product of graphs

For a graph G, κ(G) denotes its connectivity. The Kronecker product G₁×G₂ of graphs G₁ and G₂ is the graph with the vertex set V(G₁)×V(G₂), two vertices (u₁,v₁) and (u₂,v₂) being adjacent in G₁×G₂ if and only if u₁u₂∈E(G₁) and v₁v₂∈E(G₂). Guji and Vumar [R. Guji, E. Vumar, A note on the connectivity of Kronecker products of graphs, Appl. Math. Lett. 22 (2009) 1360–1363] conjectured that for any nontrivial graph G, κ(G×K_n)=min{nκ(G),(n−1)δ(G)} when n≥3. In this note, we confirm this conjecture to be true.     

Domination and upper domination of direct product graphs

Let $X_{\mathbb{Z}∕n\mathbb{Z}}$ denote the unitary Cayley graph of $\mathbb{Z}∕n\mathbb{Z}$. We present results on the tightness of the known inequality $\gamma \left(X_{\mathbb{Z}∕n\mathbb{Z}}\right)\le {\gamma }_t\left(X_{\mathbb{Z}∕n\mathbb{Z}}\right)\le g\left(n\right)$, where $\gamma$ and${\gamma }_t$ denote the domination number and total domination number, respectively, and $g$ is the arithmetic function known as Jacobsthal’s function. In particular, we construct integers $n$ with arbitrarily many distinct prime factors such that $\gamma \left(X_{\mathbb{Z}∕n\mathbb{Z}}\right)\le {\gamma }_t\left(X_{\mathbb{Z}∕n\mathbb{Z}}\right)\le g\left(n\right)?1$. We give lower bounds for the domination numbers of direct products of complete graphs and present a conjecture for the exact values of the upper domination numbers of direct products of balanced, complete multipartite graphs.     

The competition numbers of complete tripartite graphs

For a graph G, it is known to be a hard problem to compute the competition number k(G) of the graph G in general. In this paper, we give an explicit formula for the competition numbers of complete tripartite graphs.     

The edge version of Hadwiger’s conjecture

A well known conjecture of Hadwiger asserts that K_n+1 is the only minor minimal graph of chromatic number greater than n. In this paper, all minor minimal graphs of chromatic index greater than n are determined.     

广义友谊图乘积上的Graham pebbling猜想

连通图G的pebbling数f(G)是最小的正整数n,使得不管n个pebble如何放置在G的顶点上,总可以通过一系列的pebbling移动把一个pebble移到图G的任意一个顶点上.Graham猜测对于任意的连通图G和H有f(G×H)≤f(G)f(H).文中证明了当H为友谊图或广义友谊图,G是一个具有2-pebbling性质的图时,Graham猜想成立.作为一个推论,文中也证明了当G和H是友谊图或广义友谊图时,Graham猜想成立.     

Game chromatic number of strong product graphs

The graph coloring game is a two-player game in which the two players properly color an uncolored vertex of G alternately. The first player wins the game if all vertices of G are colored, and the second wins otherwise. The game chromatic number of a graph G is the minimum integer k such that the first player has a winning strategy for the graph coloring game on G with k colors. There is a lot of literature on the game chromatic number of graph products, e.g., the Cartesian product and the lexicographic product. In this paper, we investigate the game chromatic number of the strong product of graphs, which is one of major graph products. In particular, we completely determine the game chromatic number of the strong product of a double star and a complete graph. Moreover, we estimate the game chromatic number of some King's graphs, which are the strong products of two paths.     

The Erd s-Sós conjecture for graphs of girth 5

We prove that every graph of girth at least 5 with minimum degree δ k/2 contains every tree with k edges, whose maximum degree does not exceed the maximum degree of the graph. An immediate consequence is that the famous Erd s-Sós Conjecture, saying that every graph of order n with more than n(k − 1)/2 edges contains every tree with k edges, is true for graphs of girth at least 5.     

A new class of antimagic Cartesian product graphs

An antimagic labeling of a finite undirected simple graph with m edges and n vertices is a bijection from the set of edges to the integers 1,…,m such that all n-vertex sums are pairwise distinct, where a vertex sum is the sum of labels of all edges incident with the same vertex. A graph is called antimagic if it has an antimagic labeling. In 1990, Hartsfield and Ringel [N. Hartsfield, G. Ringel, Pearls in Graph Theory, Academic Press, INC., Boston, 1990, pp. 108-109, Revised version, 1994] conjectured that every simple connected graph, except K₂, is antimagic. In this article, we prove that a new class of Cartesian product graphs are antimagic. In particular, by combining this result and the antimagicness result on toroidal grids (Cartesian products of two cycles) in [Tao-Ming Wang, Toroidal grids are anti-magic, in: Proc. 11th Annual International Computing and Combinatorics Conference COCOON’2005, in: LNCS, vol. 3595, Springer, 2005, pp. 671-679], all Cartesian products of two or more regular graphs of positive degree can be proved to be antimagic.     

Distinguishing chromatic numbers of complements of Cartesian products of complete graphs

The distinguishing chromatic number of a graph, $G$, is the minimum number of colours required to properly colour the vertices of $G$ so that the only automorphism of $G$ that preserves colours is the identity. There are many classes of graphs for which the distinguishing chromatic number has been studied, including Cartesian products of complete graphs (Jerebic and Klav?ar, 2010). In this paper we determine the distinguishing chromatic number of the complement of the Cartesian product of complete graphs, providing an interesting class of graphs, some of which have distinguishing chromatic number equal to the chromatic number, and others for which the difference between the distinguishing chromatic number and chromatic number can be arbitrarily large.     

On the Crossing Number of <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">m</Emphasis></Subscript> □ <Emphasis Type="Italic">P</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>

Crossing numbers of graphs are in general very difficult to compute. There are several known exact results on the crossing number of the Cartesian products of paths, cycles or stars with small graphs. In this paper we study cr(K_m □ P_n), the crossing number of the Cartesian product K_m □ P_n. We prove that for m ≥ 3,n ≥ 1 and cr(K_m □ P_n)≥ (n − 1)cr(K_m+2 − e) + 2cr(K_m+1). For m≤ 5, according to Klešč, Jendrol and Ščerbová, the equality holds. In this paper, we also prove that the equality holds for m = 6, i.e., cr(K₆ □ P_n) = 15n + 3. Research supported by NFSC (60373096, 60573022).     

Decompositions of complete multipartite graphs

This paper answers a recent question of Dobson and Maruši? by partitioning the edge set of a complete bipartite graph into two parts, both of which are edge sets of arc-transitive graphs, one primitive and the other imprimitive. The first member of the infinite family is the one constructed by Dobson and Maruši?.     

The distinguishing chromatic number of Cartesian products of two complete graphs

A labeling of a graph G is distinguishing if it is only preserved by the trivial automorphism of G. The distinguishing chromatic number of G is the smallest integer k such that G has a distinguishing labeling that is at the same time a proper vertex coloring. The distinguishing chromatic number of the Cartesian product is determined for all k and n. In most of the cases it is equal to the chromatic number, thus answering a question of Choi, Hartke and Kaul whether there are some other graphs for which this equality holds.