Characterization of the cartesian product of complete graphs by convex subgraphs

✍ Scribed by Yoshimi Egawa

• Publisher: Elsevier Science
• Year: 1986
• Tongue: English
• Weight: 115 KB
• Volume: 58
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(86)90149-4

✦ Synopsis

We show that if G is a connected graph with the same proper convex subgraphs as (Kn)', the Cartesian product of r copies of Kn, r >t 2, n >t 3, then [V(G)I ~> n" with equality if and only if G is isomorphic to (Kn)'.

In this note we consider only connected finite undirected simple graphs. The complete graph of order n is denoted by K,. The graph obtained by deleting an edge from Ks is denoted by J,,, n >I 3. For any graph G, we let V(G) and E(G) denote the vertex set and the edge set of G, respectively. For any two graphs G1, G2, we let G, x G2 denote the Cartesian product of G1 and G2, that is to say,

x2), (y,, Y2))Ix,=y, and (x2, Y2) • E(G2), or (x,, y,) • E(GO and x2 = Y2}.

Let G be a graph. An induced subgraph H of G is said to be convex if for any two vertices x, y • V(H), H contains all paths joining x and y in G with minimum length. By a proper convex subgraph, we mean a convex subgraph which is not the empty graph or the whole graph. We let ~(G) denote the set of isomorphism classes of graphs which appear as a proper convex subgraph of G.

The purpose of this note is to remark that the result of Cruyce [1] can be generalized as follows.

Theorem. Let hi, . . . , n, be a sequence of integers such that ni >t 2 for all i, r >I 2, and let G be a graph with ~(G) = ~ (Kn, x . . . x Kn,). Assume that either ni >t 3 for some i or r>~3. Then IV(G)I >~n,. '.nr with equality if and only if G = Kn, x...xK,.