The crossing number of <Emphasis Type="Italic">G</Emphasis> ▭ <Emphasis Type="Italic">C</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript> for the graph <Emphasis Type="Italic">G</Emphasis> on six vertices

The crossing numbers of Cartesian products of paths, cycles or stars with all graphs of order at most four are known. The crossing numbers of G□C _n for some graphs G on five and six vertices and the cycle C _n are also given. In this paper, we extend these results by determining the crossing number of the Cartesian product G □ C _n , where G is a specific graph on six vertices.     

The Crossing Number of Cartesian Products of Complete Bipartite Graphs K 2, m with Paths P n

Most results on the crossing number of a graph focus on the special graphs, such as Cartesian products of small graphs with paths P_n, cycles C_n or stars S_n. In this paper, we extend the results to Cartesian products of complete bipartite graphs K_2,m with paths P_n for arbitrary m ≥ 2 and n ≥ 1. Supported by the NSFC (No. 10771062) and the program for New Century Excellent Talents in University.     

On the Maximum Number of Cliques in a Graph

A clique is a set of pairwise adjacent vertices in a graph. We determine the maximum number of cliques in a graph for the following graph classes: (1) graphs with n vertices and m edges; (2) graphs with n vertices, m edges, and maximum degree Δ; (3) d-degenerate graphs with n vertices and m edges; (4) planar graphs with n vertices and m edges; and (5) graphs with n vertices and no K₅-minor or no K_3,3-minor. For example, the maximum number of cliques in a planar graph with n vertices is 8(n − 2). Research supported by a Marie Curie Fellowship of the European Community under contract 023865, and by the projects MCYT-FEDER BFM2003-00368 and Gen. Cat 2001SGR00224.     

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.     

On the crossing numbers of Cartesian products with trees

Zip product was recently used in a note establishing the crossing number of the Cartesian product K₁,n □ P_m. In this article, we further investigate the relations of this graph operation with the crossing numbers of graphs. First, we use a refining of the embedding method bound for crossing numbers to weaken the connectivity condition under which the crossing number is additive for the zip product. Next, we deduce a general theorem for bounding the crossing numbers of (capped) Cartesian product of graphs with trees, which yields exact results under certain symmetry conditions. We apply this theorem to obtain exact and approximate results on crossing numbers of Cartesian product of various graphs with trees. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 287–300, 2007     

Two characterizations of chain partitioned probe graphs

Chain graphs are exactly bipartite graphs without induced 2K ₂ (a graph with four vertices and two disjoint edges). A graph G=(V,E) with a given independent set S⊆V (a set of pairwise non-adjacent vertices) is said to be a chain partitioned probe graph if G can be extended to a chain graph by adding edges between certain vertices in S. In this note we give two characterizations for chain partitioned probe graphs. The first one describes chain partitioned probe graphs by six forbidden subgraphs. The second one characterizes these graphs via a certain “enhanced graph”: G is a chain partitioned probe graph if and only if the enhanced graph G ^* is a chain graph. This is analogous to a result on interval (respectively, chordal, threshold, trivially perfect) partitioned probe graphs, and gives an O(m ²)-time recognition algorithm for chain partitioned probe graphs.     

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

Hedetniemi’s Conjecture and Dense Boolean Lattices

The category D{\mathcal{D}} of finite directed graphs is Cartesian closed, hence it has a product and exponential objects. For a fixed K, let K^DK^{\mathcal{D}} be the class of all directed graphs of the form K ^G , preordered by the existence of homomorphisms, and factored by homomorphic equivalence. It has long been known that K^DK^{\mathcal{D}} is always a Boolean lattice. In this paper we prove that for any complete graph K _n with n ≥ 3, K_n^DK_n^{\mathcal{D}} is dense, hence up to isomorphism it is the unique countable dense Boolean lattice. In graph theory, the structure of K_n^DK_n^{\mathcal{D}} is connected to the conjecture of Hedetniemi on the chromatic number of a categorical product of graphs.     

Small Edge Sets Meeting all Triangles of a Graph

It was conjectured in 1981 by the third author that if a graph G does not contain more than t pairwise edge-disjoint triangles, then there exists a set of at most 2t edges that shares an edge with each triangle of G. In this paper, we prove this conjecture for odd-wheel-free graphs and for ‘triangle-3-colorable’ graphs, where the latter property means that the edges of the graph can be colored with three colors in such a way that each triangle receives three distinct colors on its edges. Among the consequences we obtain that the conjecture holds for every graph with chromatic number at most four. Also, two subclasses of K ₄-free graphs are identified, in which the maximum number of pairwise edge-disjoint triangles is equal to the minimum number of edges covering all triangles. In addition, we prove that the recognition problem of triangle-3-colorable graphs is intractable.     

The Crossing Number of C(8, 2)□P n

C(n, k) is a graph obtained from n-cycle by adding edges v _i v _i+k (i = 1, 2,...,n, i + k (mod n)). There are several known results on the crossing numbers of the Cartesian products of C(n, k) (n ≤ 7) with paths, cycles and stars. In this paper we extend these results, and show that the crossing number of the Cartesian product of C(8, 2) with P _n is 8n. Yuanqiu Huang: Research supported by NSFC (10771062) and New Century Excellent Talents in University (NCET-07-0276). Jinwang Liu: Research supported by NSFC (10771058) and Hunan NSFC(O6jj20053).     

Characterizing subgraphs of Hamming graphs

Cartesian products of complete graphs are known as Hamming graphs. Using embeddings into Cartesian products of quotient graphs we characterize subgraphs, induced subgraphs, and isometric subgraphs of Hamming graphs. For instance, a graph G is an induced subgraph of a Hamming graph if and only if there exists a labeling of E(G) fulfilling the following two conditions: (i) edges of a triangle receive the same label; (ii) for any vertices u and v at distance at least two, there exist two labels which both appear on any induced u, υ‐path. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 302–312, 2005     

On anti-magic labeling for graph products

An anti-magic labeling of a finite simple undirected graph with p vertices and q edges is a bijection from the set of edges to the set of integers {1,2,…,q} such that the vertex sums are pairwise distinct, where the vertex sum at one vertex is the sum of labels of all edges incident to such vertex. A graph is called anti-magic if it admits an anti-magic labeling. Hartsfield and Ringel conjectured in 1990 that all connected graphs except K₂ are anti-magic. Recently, Alon et al. showed that this conjecture is true for dense graphs, i.e. it is true for p-vertex graphs with minimum degree Ω(logp). In this article, new classes of sparse anti-magic graphs are constructed through Cartesian products and lexicographic products.     

On Partitional and Other Related Graphs

The partitional graphs, which are a subclass of the sequential graphs, were recently introduced by Ichishima and Oshima (Math Comput Sci 3:39–45, 2010), and the cartesian product of a partitional graph and K ₂ was shown to be partitional, sequential, harmonious and felicitous. In this paper, we present some necessary conditions for a graph to be partitional. By means of these, we study the partitional properties of certain classes of graphs. In particular, we completely characterize the classes of the graphs B _m and K _m,2 × Q _n that are partitional. We also establish the relationships between partitional graphs and graphs with strong α-valuations as well as strongly felicitous graphs.     

The Number of Spanning Trees in <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>-Complements of Quasi-Threshold Graphs

In this paper we examine the classes of graphs whose K_n-complements are trees or quasi-threshold graphs and derive formulas for their number of spanning trees; for a subgraph H of K_n, the K_n-complement of H is the graph K_n–H which is obtained from K_n by removing the edges of H. Our proofs are based on the complement spanning-tree matrix theorem, which expresses the number of spanning trees of a graph as a function of the determinant of a matrix that can be easily constructed from the adjacency relation of the graph. Our results generalize previous results and extend the family of graphs of the form K_n–H admitting formulas for the number of their spanning trees.Final version received: March 18, 2004     

Vertex Partitions of K4,4-Minor Free Graphs

 We prove that a 4-connected K _4,4-minor free graph on n vertices has at most 4n−8 edges and we use this result to show that every K _4,4-minor free graph has vertex-arboricity at most 4. This improves the case (n,m)=(7,3) of the following conjecture of Woodall: the vertex set of a graph without a K _n -minor and without a -minor can be partitioned in n−m+1 subgraphs without a K _m -minor and without a -minor. Received: January 7, 1998 Final version received: May 17, 1999     

On two Hamilton cycle problems in random graphs

We study two problems related to the existence of Hamilton cycles in random graphs. The first question relates to the number of edge disjoint Hamilton cycles that the random graph G _n,p contains. δ(G)/2 is an upper bound and we show that if p ≤ (1 + o(1)) ln n/n then this upper bound is tight whp. The second question relates to how many edges can be adversarially removed from G _n,p without destroying Hamiltonicity. We show that if p ≥ K ln n/n then there exists a constant α > 0 such that whp G − H is Hamiltonian for all choices of H as an n-vertex graph with maximum degree Δ(H) ≤ αK ln n. Research supported in part by NSF grant CCR-0200945. Research supported in part by USA-Israel BSF Grant 2002-133 and by grant 526/05 from the Israel Science Foundation.     

Subdirect Decomposition of n-Chromatic Graphs

It is shown that any n-chromatic graph is a full subdirect product of copies of the complete graphs K _n and K _n+1, except for some easily described graphs which are full subdirect products of copies of K _n+1 - {°-°} and K _n+2 - {°-°}; full means here that the projections of the decomposition are epimorphic in edges. This improves some results of Sabidussi. Subdirect powers of K _n or K _n+1 - {°-°} are also characterized, and the subdirectly irreducibles of the quasivariety of n -colorable graphs with respect to full and ordinary decompositions are determined.     

Folding Wheels and Fans

 If two non-adjacent vertices of a connected graph that have a common neighbor are identified and the resulting multiple edges are reduced to simple edges, then we obtain another graph of order one less than that of the original graph. This process can be repeated until the resulting graph is complete. We say that we have folded the graph onto complete graph. This process of folding a connected graph G onto a complete graph induces in a very natural way a partition of the vertex-set of G. We denote by F(G) the set of all complete graphs onto which G can be folded. We show here that if p and q are the largest and smallest orders, respectively, of the complete graph in F(W _n ) or F(F _n ), then K _s is in F(W _n ) or F(F _n ) for each s, q≤s≤p. Lastly, we shall also determine the exact values of p and q. Received: October, 2001 Final version received: June 26, 2002     

Large Monotone Paths in Graphs with Bounded Degree

 We prove that for every ε>0 and positive integer r, there exists Δ₀=Δ₀(ε) such that if Δ>Δ₀ and n>n(Δ,ε,r) then there exists a packing of K _n with ⌊(n−1)/Δ⌋ graphs, each having maximum degree at most Δ and girth at least r, where at most εn ² edges are unpacked. This result is used to prove the following: Let f be an assignment of real numbers to the edges of a graph G. Let α(G,f) denote the maximum length of a monotone simple path of G with respect to f. Let α(G) be the minimum of α(G,f), ranging over all possible assignments. Now let α_Δ be the maximum of α(G) ranging over all graphs with maximum degree at most Δ. We prove that Δ+1≥α_Δ≥Δ(1−o(1)). This extends some results of Graham and Kleitman [6] and of Calderbank et al. [4] who considered α(K _n ). Received: March 15, 1999?Final version received: October 22, 1999     

On Super Restricted Edge Connectivity of Half Vertex Transitive Graphs

Let X =  (V, E) be a connected graph. Call X super restricted edge connected in short, sup-λ′, if F is a minimum edge set of X such that X − F is disconnected and every component of X − F has at least two vertices, then F is the set of edges adjacent to a certain edge with minimum edge degree in X. A bipartite graph is said to be half vertex transitive if its automorphism group is transitive on the sets of its bipartition. In this article, we show that every connected half vertex transitive graph X with n =  |V(X)| ≥  4 and X \ncong K_1,n-1{X \ncong K_{1,n-1}} is λ′-optimal. By studying the λ′-superatoms of X, we characterize sup-λ′ connected half vertex transitive graphs. As a corollary, sup-λ′ connected Bi-Cayley graphs are also characterized.