10 citations · 19 across the 21 of their papers we have counts for
22 papers · 1 filter
Duality and minors for embeddings of graphs in pseudosurfaces
Blake Dunshee, M. N. Ellingham, Joanna A. Ellis-Monaghan
Cellular embeddings of graphs in surfaces have well-defined duality and minor (edge contraction and deletion) operations that interact in a natural way. A pseudosurface is obtained…
Polynomial invariants of cyclically ordered graphs
Paul Bratch, M. N. Ellingham, Joanna A. Ellis-Monaghan +2
Cyclically ordered graphs, or cogs, sit between abstract graphs and cellularly embedded graphs. They arise naturally in topological graph theory, knot theory, and mathematical biol…
Bipartite holes, degree sums and Hamilton cycles
Mark Ellingham, Yixuan Huang, Bing Wei
The {\em bipartite-hole-number} of a graph , denoted as , is the minimum number such that there exist integers and with such that for a…
Forbidding the subdivided claw as a subgraph or a minor
Sarah Allred, M. N. Ellingham
Let be the subdivided claw, the -vertex tree obtained from a claw by subdividing each edge exactly once. We characterize the graphs (finite and infinite) that do n…
Unavoidable substructures in large and infinite -edge-connected graphs
Sarah Allred, M. N. Ellingham
In 1930, Ramsey proved that every large graph contains either a large clique or a large edgeless graph as an induced subgraph. It is well known that every large connected graph con…
A Fano framework for embeddings of graphs in surfaces
Blake Dunshee, M. N. Ellingham
We consider seven fundamental properties of cellular embeddings of graphs in compact surfaces, and show that each property can be associated with a point of the Fano plane , in…
Spanning weakly even trees of graphs
Jiangdong Ai, M. N. Ellingham, Zhipeng Gao +5
Let be a graph (with multiple edges allowed) and let be a tree in . We say that is if every leaf of belongs to the same part of the bipartition o…
Maximum genus embeddings of dense eulerian graphs with specified faces
M. N. Ellingham, Joanna A. Ellis-Monaghan
We give a density condition for when, subject to a necessary parity condition, an eulerian graph or digraph may be cellularly embedded in an orientable surface so that it has exact…
A Catalog of Enumeration Formulas for Bouquet and Dipole Embeddings Under Symmetries
M. N. Ellingham, Joanna A. Ellis-Monaghan
Motivated by a problem arising out of DNA origami, we give a general counting framework and enumeration formulas for various cellular embeddings of bouquets and dipoles under diffe…
Maximum spectral radius of outerplanar 3-uniform hypergraphs
M. N. Ellingham, Linyuan Lu, Zhiyu Wang
In this paper, we study the maximum spectral radius of outerplanar -uniform hypergraphs. Given a hypergraph , the shadow of is a graph with $V(G)=…
Toughness and prism-hamiltonicity of -free graphs
M. N. Ellingham, Pouria Salehi Nowbandegani, Songling Shan
The \emph{prism} over a graph is the product , i.e., the graph obtained by taking two copies of and adding a perfect matching joining the two copies of each ver…
The Chvátal-Erdős condition for prism-Hamiltonicity
M. N. Ellingham, Pouria Salehi Nowbandegani
The prism over a graph is the cartesian product . It is known that the property of having a Hamiltonian prism (prism-Hamiltonicity) is stronger than that of having…
Edge-outer graph embedding and the complexity of the DNA reporter strand problem
M. N. Ellingham, Joanna A. Ellis-Monaghan
In 2009, Jonoska, Seeman and Wu showed that every graph admits a route for a DNA reporter strand, that is, a closed walk covering every edge either once or twice, in opposite direc…
Toughness and spanning trees in -minor-free graphs
M. N. Ellingham, Songling Shan, Dong Ye +1
For an integer , a -tree is a tree with maximum degree at most . More generally, if is an integer-valued function on vertices, an -tree is a tree in which each vert…
Hamiltonicity of planar graphs with a forbidden minor
M. N. Ellingham, Emily A. Marshall, Kenta Ozeki +1
Tutte showed that -connected planar graphs are Hamiltonian, but it is well known that -connected planar graphs need not be Hamiltonian. We show that -minor-free -…
Spanning trails with maximum degree at most 4 in -free graphs
Guantao Chen, M. N. Ellingham, Akira Saito +1
A graph is called -free if it does not contain two independent edges as an induced subgraph. Mou and Pasechnik conjectured that every -tough -free graph wi…
Quadrangular embeddings of complete graphs and the Even Map Color Theorem (with details)
Wenzhong Liu, Serge Lawrencenko, Beifang Chen +5
Hartsfield and Ringel constructed orientable quadrangular embeddings of the complete graph for , and nonorientable ones for and $n\equiv 1 \pmod…
One-way infinite 2-walks in planar graphs
Daniel P. Biebighauser, M. N. Ellingham
We prove that every 3-connected 2-indivisible infinite planar graph has a 1-way infinite 2-walk. (A graph is 2-indivisible if deleting finitely many vertices leaves at most one inf…
Partial duality and closed 2-cell embeddings
M. N. Ellingham, Xiaoya Zha
In 2009 Chmutov introduced the idea of partial duality for embeddings of graphs in surfaces. We discuss some alternative descriptions of partial duality, which demonstrate the symm…
A characterization of -minor-free graphs
M. N. Ellingham, Emily A. Marshall, Kenta Ozeki +1
We provide a complete structural characterization of -minor-free graphs. The -connected -minor-free graphs consist of nine small graphs on at most eight vertic…
Criticality of counterexamples to toroidal edge-hamiltonicity
M. N. Ellingham, Emily A. Marshall
A well-known conjecture of Grünbaum and Nash-Williams proposes that 4-connected toroidal graphs are hamiltonian. The corresponding results for 4-connected planar and projective-pla…
Orientable embeddings and orientable cycle double covers of projective-planar graphs
M. N. Ellingham, Xiaoya Zha
In a closed 2-cell embedding of a graph each face is homeomorphic to an open disk and is bounded by a cycle in the graph. The Orientable Strong Embedding Conjecture says that every…