11 citations · 27 across the 16 of their papers we have counts for
15 papers · 1 filter
Sunlet factors for Cartesian products of cycles
Henry Jervis, Paul C. Kainen
A sunlet is a cycle with a pendant edge attached at each vertex of the cycle. For the bipartite toroidal grid graphs , factorizations into sunlets are given by…
Skewness, crossing number and Euler's bound for graphs on surfaces
Paul C. Kainen
For every connected graph and surface , we consider the well-known string of inequalities , where and denote skewness and crossing nu…
Star arboricity relaxed book thickness of
Paul C. Kainen
A book embedding of the complete graph needs pages and the page-subgraphs can be chosen to be spanning paths (for even) and one spanning star…
Complexity of graph evolutions
Jeffrey Gao, Paul C. Kainen
A permutation of the elements of a graph is a {\it construction sequence} if no edge is listed before either of its endpoints. The complexity of such a sequence is investigated by…
All bipartite circulants are dispersable
Shannon Overbay, Samuel Joslin, Paul C. Kainen
We show that a cyclic vertex order due to Yu, Shao and Li gives a dispersable book embedding for any bipartite circulant.
Eulerian 2-Complexes
Richard H. Hammack, Paul C. Kainen
It is shown that Euler's theorem for graphs can be generalized for 2-complexes. Two notions that generalize cycle and Eulerian tour are introduced (``circlet'' and ``Eulerian cover…
A new view of hypercube genus
Richard H. Hammack, Paul C. Kainen
Beineke, Harary and Ringel discovered a formula for the minimum genus of a torus in which the -dimensional hypercube graph can be embedded. We give a new proof of the formula by…
Graph embeddings with no Hamiltonian extensions
Paul C. Kainen, Shannon Overbay
We show that extending an embedding of a graph in a surface to an embedding of a Hamiltonian supergraph can be blocked by certain planar subgraphs but, for some subdivisions of…
Canonical Sphere Bases for Simplicial and Cubical Complexes
Paul C. Kainen
Sphere-bases are constructed for the vector space formed by the -dimensional subcomplexes, of -simplex (or -cube), for which every -face is contain…
Construction numbers: How to build a graph?
Paul C. Kainen
A construction sequence for a graph is a listing of the elements of the graph (the set of vertices and edges) such that each edge follows both its endpoints. The construction numbe…
Book embeddings of graphs and a theorem of Whitney
Paul C. Kainen, Shannon Overbay
It is shown that the number of pages required for a book embedding of a graph is the maximum of the numbers needed for any of the maximal nonseparable subgraphs and that a plane gr…
On dispersability of some circulant graphs
Paul C. Kainen, Samuel S. Joslin, Shannon Overbay
The matching book thickness of a graph is the least number of pages in a book embedding such that each page is a matching. A graph is dispersable if its matching book thickness equ…
On dispersability of some products of cycles
Samuel S. Joslin, Paul C. Kainen, Shannon Overbay
We show that the matching book thickness of the Cartesian product of two odd-length cycle-graphs is five if at least one of the cycles has length 3 or 5.
Factorization of Platonic Polytopes into canonical spheres
R. H. Hammack, P. C. Kainen
Factorization into spheres is achieved for skeleta of the simplex, cube, and cross-polytope, both explicitly and using Keevash's proof of existence of designs.
Cubic planar bipartite graphs are dispersable
Paul C. Kainen, Shannon Overbay
A graph is called dispersable if it has a book embedding in which each page has maximum degree 1 and the number of pages is the maximum degree. Bernhart and Kainen conjectured ever…