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

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 .     

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数

图 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.     

$K_v$的最大$K_2K_3$填充设计

Abstract Let Kv be the complete graph on v vertices, and G a finite simple undirected graph without isolated vertices. A G-packing of Kv, denoted by （v, G, 1）-packing, is a pair （X,A） where X is the vertex set of K＋ and ＋4 is a family of edge-disjoint subgraphs isomorphic to G in Kv. In this paper, the maximum number of subgraphs in a （v, G, 1）-packing is determined when G is K2 x K3, the Cartesian product of K2 and K3, leaving two orders undetermined. This design originated from the use of DNA library screening.     

Cube intersection concepts in median graphs

In this paper, we study different classes of intersection graphs of maximal hypercubes of median graphs. For a median graph G and k≥0, the intersection graph Q_k(G) is defined as the graph whose vertices are maximal hypercubes (by inclusion) in G, and two vertices H_x and H_y in Q_k(G) are adjacent whenever the intersection H_x∩H_y contains a subgraph isomorphic to Q_k. Characterizations of clique-graphs in terms of these intersection concepts when k>0, are presented. Furthermore, we introduce the so-called maximal 2-intersection graph of maximal hypercubes of a median graph G, denoted , whose vertices are maximal hypercubes of G, and two vertices are adjacent if the intersection of the corresponding hypercubes is not a proper subcube of some intersection of two maximal hypercubes. We show that a graph H is diamond-free if and only if there exists a median graph G such that H is isomorphic to . We also study convergence of median graphs to the one-vertex graph with respect to all these operations.     

Cartesian products of directed graphs with loops

We show that every nontrivial finite or infinite connected directed graph with loops and at least one vertex without a loop is uniquely representable as a Cartesian or weak Cartesian product of prime graphs. For finite graphs the factorization can be computed in linear time and space.     

Vertex coloring complete multipartite graphs from random lists of size 2

Let K_s×m be the complete multipartite graph with s parts and m vertices in each part. Assign to each vertex v of K_s×m a list L(v) of colors, by choosing each list uniformly at random from all 2-subsets of a color set C of size σ(m). In this paper we determine, for all fixed s and growing m, the asymptotic probability of the existence of a proper coloring φ, such that φ(v)∈L(v) for all v∈V(K_s×m). We show that this property exhibits a sharp threshold at σ(m)=2(s−1)m.     

Equistable graphs, general partition graphs, triangle graphs, and graph products

In this paper we examine the connections between equistable graphs, general partition graphs and triangle graphs. While every general partition graph is equistable and every equistable graph is a triangle graph, not every triangle graph is equistable, and a conjecture due to Jim Orlin states that every equistable graph is a general partition graph. The conjecture holds within the class of chordal graphs; if true in general, it would provide a combinatorial characterization of equistable graphs.Exploiting the combinatorial features of triangle graphs and general partition graphs, we verify Orlin’s conjecture for several graph classes, including AT-free graphs and various product graphs. More specifically, we obtain a complete characterization of the equistable graphs that are non-prime with respect to the Cartesian or the tensor product, and provide some necessary and sufficient conditions for the equistability of strong, lexicographic and deleted lexicographic products. We also show that the general partition graphs are not closed under the strong product, answering a question by McAvaney et al.     

W6*Sn的交叉数

早在20世纪50年代,Zarankiewicz 猜想完全2-部图K_{m,n}(mleq n)的交叉数为lfloorfrac{m}{2}rfloortimes lfloorfrac{m-1}{2}rfloortimeslfloorfrac{n}{2}rfloortimeslfloorfrac{n-1}{2}rfloor (对任意实数x,lfloor xrfloor表示不超过x的最大整数). 目前这一猜想的正确性只证明了当mleq6时成立. 假定著名的Zarankiewicz的猜想对m=7的情形成立,确定了6-轮W_{6}与星S_{n}的笛卡尔积图的交叉是 cr(W_{6}times S_{n})=9lfloorfrac{n}{2}rfloortimeslfloorfrac{n-1}{2}rfloor+2n+5lfloorfrac{n}{2}rfloor.     

K_m~-□P_n的交叉数

Klesc等人先后确定了K_m~-□P_n(4≤m≤6)的交叉数,本文利用构造法确定了K_m-2K_2(4≤m≤12,m≠10,12)的交叉数.在此基础上,可进一步确定K_m~-□P_n(4≤m≤9,m≠8)的交叉数.相比而言,我们所采用的方法更具一般性.     

Products of unit distance graphs

Some graphs admit drawings in the Euclidean plane (k-space) in such a (natural) way, that edges are represented as line segments of unit length. We say that they have the unit distance property.The influence of graph operations on the unit distance property is discussed. It is proved that the Cartesian product preserves the unit distance property in the Euclidean plane, while graph union, join, tensor product, strong product, lexicographic product and corona do not. It is proved that the Cartesian product preserves the unit distance property also in higher dimensions.     

SOME PROPERTIES OF A CLASS OF INTERCHANGE GRAPHS

§１ＩｎｔｒｏｄｕｃｔｉｏｎＬｅｔＧｂｅａｃｏｎｎｅｃｔｅｄｇｒａｐｈｗｉｔｈｖｅｒｔｅｘ－ｓｅｔＶ（Ｇ）ａｎｄｅｄｇｅ－ｓｅｔＥ（Ｇ）．Ｄｅｎｏｔｅｂｙｅ＝（ｘ，ｙ）ｔｈｅｅｄｇｅｊｏｉｎｉｎｇｔｈｅｖｅｒｔｉｃｅｓｘａｎｄｙｏｆＧ．Ａｍ－ｃｌｉｑ...     

Wide diameter of Cartesian graph bundles

Fault tolerance and transmission delay of networks are important concepts in network design. The notions are strongly related to connectivity and diameter of a graph, and have been studied by many authors. Wide diameter of a graph combines studying connectivity with the diameter of a graph. Diameter with width k of a graph G, k-diameter, is defined as the minimum integer d for which there exist at least k internally disjoint paths of length at most d between any two distinct vertices in G. Denote by D_c(G) the c-diameter of G and κ(G) the connectivity of G. In the context of computer networks, wide diameters of Cartesian graph products have been recently studied by many authors. Cartesian graph bundles is a class of graphs that is a generalization of the Cartesian graph products. Let G be a Cartesian graph bundle with fiber F over base B, 0<a≤κ(F), and 0<b≤κ(B). We prove that D_a+b(G)≤D_a(F)+D_b(B)+1. Moreover, if G is a graph bundle with fiber F≠K₂ over base B≠K₂, then D_a+b(G)≤D_a(F)+D_b(B). The bounds are tight.     

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.     

Fall colouring of bipartite graphs and cartesian products of graphs

The question of whether a graph can be partitioned into k independent dominating sets, which is the same as having a fallk-colouring, is considered. For k=3, it is shown that a graph G can be partitioned into three independent dominating sets if and only if the cartesian product G□K₂ can be partitioned into three independent dominating sets. The graph K₂ can be replaced by any graph H such that there is a mapping f:Q_n→H, where f is a type-II graph homomorphism.The cartesian product of two trees is considered, as well as the complexity of partitioning a bipartite graph into three independent dominating sets, which is shown to be NP-complete. For other values of k, iterated cartesian products are considered, leading to a result that shows for what values of k the hypercubes can be partitioned into k independent dominating sets.     

On constructing normal and non-normal Cayley graphs

Bamberg and Giudici (2011) showed that the point graphs of certain generalised quadrangles of order $(q?1,q+1)$, where $q=p^k$ is a prime power with $p\ge 5$, are both normal and non-normal Cayley graphs for two isomorphic groups. We call these graphs BG-graphs. In this paper, we show that the Cayley graphs obtained from a finite number of BG-graphs by Cartesian product, direct product, and strong product also possess the property of being normal and non-normal Cayley graphs for two isomorphic groups.