Bounded Complete Embedding Graphs

Abstract

In the study of graph embeddings, there is particular interest in small embeddings and in bounds on the minimum number of vertices that must be added in order to achieve an embedding of a particular design. We introduce two new terms, defining a natural approach to the bounding question. A simple graph G is a bounded complete embedding graph if and only if there is some positive integer b such that, for every positive integer n such that a complete G-design of order n exists, every complete G-design of order n can be embedded in a complete G-design of order (n + x), for some positive integer x that is at most b. A simple graph G is a bounded embedding graph if and only if there is some positive integer c such that, for every positive integer n, every partial G-design of order n can be embedded in a complete G-design of order (n + x), for some positive integer x that is at most c.

By definition, every bounded embedding graph is a bounded complete embedding graph; we show that the converse of this fact is false, and that all bounded complete embedding graphs are bipartite. We identify results in the literature that provide, as immediate corollaries, the following results: that k-stars are bounded embedding graphs, that 3-paths are bounded embedding graphs, and that even cycles are bounded complete embedding graphs.

We establish that paths and complete bipartite graphs are bounded complete embedding graphs. We show that all simple bipartite graphs G such that the number edges in G is a positive power of two, all vertices of G have even degree, and G admits a $\beta^+$-labeling, are bounded complete embedding graphs.

We show that the (p, C_{2k})-cohort, the graph consisting of p vertex-disjoint 2k-cycles, is a bounded complete embedding graph if p is a positive power of two or if the integers p and k both belong to the closed interval [2, 128]. These results on the (p, C_{2k})-cohort and the supporting constructions comprise a major portion of our work. We produce two constructions of (p, C_{2k})-cohort-designs on complete bipartite graphs; we apply these constructions to obtain the designs on complete bipartite graphs that are necessary to build embeddings. We rely on existing graph labeling results that establish, for all values of p and k, the existence of a complete (p, C_{2k})-cohort-design of order (4kp + 1); we also present our own independently achieved designs for some values of p and k, and we compare our designs to those created by graph labelings. Furthermore, we establish the spectrum of complete (p, C_{2k})-cohort-designs when the product 4kp is a positive power of two, and we exhibit the additional designs necessary to establish the spectrum of complete (p, C_{2k})-cohort-designs for p = 2 and k either 3 or 5.