Mark Ellingham's Publications

Access to doi: links usually requires that you or your library have a subscription to the journal. Preprint versions are generally the first version submitted to a journal, before any feedback from the referees.

Submitted

• Jiangdong Ai, M. N. Ellingham, Zhipeng Gao, Yixuan Huang, Xiangzhou Liu, Songling Shan, Simon Špacapan and Jun Yue, Spanning weakly even trees of graphs, preprint. arXiv:2409.15522 (6 pages), PDF preprint.
• M. N. Ellingham and Joanna A. Ellis-Monaghan, Maximum genus embeddings of dense eulerian graphs with specified faces, submitted. arXiv:2409.14531 (32 pages), PDF preprint.
• M. N. Ellingham and Joanna A. Ellis-Monaghan, Bi-eulerian embeddings of graphs and digraphs, submitted. arXiv:2404.00325 (34 pages), PDF preprint.

Published

• M. N. Ellingham and Joanna A. Ellis-Monaghan, Maximum genus orientable embeddings from circuit decompositions of dense eulerian graphs and digraphs, Proc. 12th European Conf. on Combinatorics, Graph Theory and Applications (Prague, 2023), Masaryk University Press, 2023, 401--406. (Extended abstract for conference.) doi:10.5817/CZ.MUNI.EUROCOMB23-056, final version.
• M. N. Ellingham and Joanna A. Ellis-Monaghan, A catalog of enumeration formulas for bouquet and dipole embeddings under symmetries, Symmetry 14 no. 9 (2022) paper 1793 (39 pages). doi:10.3390/sym14091793, journal version (open access), arXiv:2206.09226 (47 pages), PDF preprint.
• Wenzhong Liu, M. N. Ellingham and Dong Ye, Minimal quadrangulations of surfaces, J. Combinatorial Theory Series B 157 (2022) 235-262. doi:10.1016/j.jctb.2022.06.003, arXiv:2106.13377, PDF preprint.
• M. N. Ellingham, Linyuan Lu and Zhiyu Wang, Maximum spectral radius of outerplanar 3-uniform hypergraphs, J. Graph Theory 100 (2022) 671-685. doi:10.1002/jgt.22801, arXiv:2010.04624v2, PDF preprint.
• M. N. Ellingham, Songling Shan, Dong Ye and Xiaoya Zha, Toughness and spanning trees in K_4-minor-free graphs, J. Graph Theory 96 (2021) 379-402. doi:10.1002/jgt.22620, arXiv:1704.00246, PDF preprint.
• M. N. Ellingham, Pouria Salehi Nowbandegani and Songling Shan, Toughness and prism-hamiltonicity of P_4-free graphs, Discrete Applied Math. 284 (2020) 201-206. doi:10.1016/j.dam.2020.03.035, arXiv:1901.01959, PDF preprint.
• M. N. Ellingham and Pouria Salehi Nowbandegani, The Chvátal-Erdős condition for prism-Hamiltonicity, Discrete Mathematics 343 (2020) 111709 (4 pages). doi:10.1016/j.disc.2019.111709, arXiv:1812.02894, PDF preprint.
• Wenzhong Liu, Serge Lawrencenko, Beifang Chen, M. N. Ellingham, Nora Hartsfield, Hui Yang, Dong Ye and Xiaoya Zha, Quadrangular embeddings of complete graphs and the Even Map Color Theorem, J. Combinatorial Theory Ser. B 139 (2019) 1-26. doi:10.1016/j.jctb.2019.02.006. Long version with added details: arXiv:1606.00948v3, PDF preprint. (Previous version: Wenzhong Liu, M. N. Ellingham, Dong Ye and Xiaoya Zha, Quadrangular embeddings of complete graphs, arXiv:1606.00948v1, PDF preprint.)
• M. N. Ellingham and Joanna A. Ellis-Monaghan, Edge-outer graph embedding and the complexity of the DNA reporter strand problem, Theor. Comput. Sci 785 (2019) 117-127. doi:10.1016/j.tcs.2019.03.019, arXiv:1710.09048, PDF preprint.
• M. N. Ellingham, Emily A. Marshall, Kenta Ozeki and Shoichi Tsuchiya, Hamiltonicity of planar graphs with a forbidden minor, J. Graph Theory, 90 (2019) 459-483. doi:10.1002/jgt.22407, arXiv:1610.06558, PDF preprint.
• Daniel P. Biebighauser and M. N. Ellingham, One-way infinite 2-walks in planar graphs, J. Graph Theory 88 (2018) 110-130. doi:10.1002/jgt.22188, arXiv:1508.06982, PDF preprint.
• Guantao Chen, M. N. Ellingham, Akira Saito and Songling Shan, Spanning trails with maximum degree at most 4 in 2K_2-free graphs, Graphs and Combinatorics 33 (2017) 1095-1101. doi:10.1007/s00373-017-1823-2, arXiv:1609.08730, PDF preprint.
• M. N. Ellingham and Xiaoya Zha, Partial duality and closed 2-cell embeddings, J. Combinatorics 8 (2017) 227-254. arXiv:1501.06043, PDF preprint (final version).
• M. N. Ellingham, Emily A. Marshall, Kenta Ozeki and Shoichi Tsuchiya, A characterization of K_{2,4}-minor-free graphs, SIAM J. Discrete Math. 30 (2016) 955-975. doi:10.1137/140986517, arXiv:1409.4632, PDF preprint (final version).
• M. N. Ellingham and Emily A. Marshall, Criticality of counterexamples to toroidal edge-hamiltonicity, Graphs and Combinatorics 32 (2016) 111-121. doi:10.1007/s00373-015-1542-5, arXiv:1312.1379, PDF preprint.
• M. N. Ellingham and Justin Z. Schroeder, Orientable hamilton cycle embeddings of complete tripartite graphs II: voltage graph constructions and applications, J. Graph Theory 77 (2014) 219-236. doi:10.1002/jgt.21783, PDF preprint.
• M. N. Ellingham and Justin Z. Schroeder, Orientable hamilton cycle embeddings of complete tripartite graphs I: latin square constructions, J. Combinatorial Designs 22 (2014) 71-94. doi:10.1002/jcd.21375, PDF preprint.
• M. N. Ellingham, Michael D. Plummer and Gexin Yu, Linkage for the diamond and the path with four vertices, J. Graph Theory 70 (2012) 241-261. doi:10.1002/jgt.20612, PDF preprint.
• M. N. Ellingham and Justin Z. Schroeder, Nonorientable hamilton cycle embeddings of complete tripartite graphs, Discrete Mathematics 312 (2012) 1911-1917. doi:10.1016/j.disc.2012.02.012, PDF preprint.
• M. N. Ellingham and Justin Z. Schroeder, Distinguishing partitions and uniform asymmetric hypergraphs, Ars Mathematica Contemporanea 4 (2011) 111-123. amc.imfm.si/index.php/amc/article/view/195, PDF preprint.
• M. N. Ellingham and Xiaoya Zha, Orientable embeddings and orientable cycle double covers of projective-planar graphs, European J. Combinatorics 32 (2011) 495-509. doi:10.1016/j.ejc.2011.01.001, arXiv:0911.2713, PDF preprint.
• M. N. Ellingham and D. Christopher Stephens, The orientable genus of some joins of complete graphs with large edgeless graphs, Discrete Math. 309 (2009) 1190-1198. doi:10.1016/j.disc.2007.12.098, PDF preprint.
• M. N. Ellingham and Adam Weaver, Constructing all minimum genus embeddings of K_{3,n}, Electronic Notes in Discrete Math. 31 (2008) 293-298. (Extended abstract for conference.) doi:10.1016/j.endm.2008.06.059.
• Daniel P. Biebighauser and M. N. Ellingham, Prism-hamiltonicity of triangulations, J. Graph Theory 57 (2008) 181-197. doi:10.1002/jgt.20276, PDF preprint.
• M. N. Ellingham and D. Christopher Stephens, The nonorientable genus of joins of complete graphs with large edgeless graphs, J. Combinatorial Theory Series B 97 (2007) 827-845. doi:10.1016/j.jctb.2007.02.001, PDF preprint.
• M. N. Ellingham and Ken-ichi Kawarabayashi, 2-connected spanning subgraphs with low maximum degree in locally planar graphs, J. Combinatorial Theory Series B 97 (2007) 401-412. doi:10.1016/j.jctb.2006.07.002, PDF preprint.
• M. N. Ellingham, Chris Stephens and Xiaoya Zha, The nonorientable genus of complete tripartite graphs, J. Combinatorial Theory Series B 96 (2006) 529-559. doi:10.1016/j.jctb.2005.10.004, PDF preprint.
• M. N. Ellingham and Chris Stephens, Triangular embeddings of complete graphs (neighborly maps) with 12 and 13 vertices, J. Combinatorial Designs 13 (2005) 336-344. doi:10.1002/jcd.20048, PDF preprint.
• M. N. Ellingham, Chris Stephens and Xiaoya Zha, Counterexamples to the nonorientable genus conjecture for complete tripartite graphs, European J. Combinatorics 26 (2005) 387-399. doi:10.1016/j.ejc.2004.01.009.
• Mark N. Ellingham, Herbert Fleischner, Martin Kochol and Emanuel Wenger, Colorability of planar graphs with isolated nontriangular faces, Graphs and Combinatorics 20 (2004) 443-446. doi:10.1007/s00373-004-0574-z.
• M. N. Ellingham, Xiaoya Zha and Yi Zhang, Spanning 2-trails from degree sum conditions, J. Graph Theory 45 (2004) 298-319. doi:10.1002/jgt.10162, PDF preprint.
• Rommel Barbosa and M. N. Ellingham, A characterisation of cubic parity graphs, Australasian J. Combinatorics 28 (2003) 273-293. PDF preprint, PDF long version with full details (2 Apr. 2003).
• M. N. Ellingham and Xiaoya Zha, Separating cycles in doubly toroidal embeddings, Graphs and Combinatorics 19 (2003) 161-175. doi:10.1007/s00373-002-0491-y, PDF preprint.
• M. N. Ellingham, Yunsun Nam and H.-J. Voss, Connected (g,f)-factors, J. Graph Theory 39 (2002) 62-75. doi:10.1002/jgt.10019.
• M. N. Ellingham and D. Kirk Menser, Girth, minimum degree and circumference, J. Graph Theory 34 (2000) 221-233. doi:10.1002/1097-0118(200007)34:3<221::AID-JGT3>3.0.CO;2-T.
• M. N. Ellingham and Xiaoya Zha, Toughness, trees and walks, J. Graph Theory 33 (2000) 125-137. doi:10.1002/(SICI)1097-0118(200003)33:3<125::AID-JGT1>3.0.CO;2-X.
• M. N. Ellingham and Xiaoya Zha, The spectral radius of graphs on surfaces, J. Combinatorial Theory Series B 78 (2000) 45-56. doi:10.1006/jctb.1999.1926.
• Y. Caro, M. N. Ellingham and J. E. Ramey, Local structure when all maximal independent sets have equal weight, SIAM J. Discrete Math. 11 (1998) 644-654. doi:10.1137/S0895480196300479
• L. Clark, M. N. Ellingham and D. K. Menser, On the circumference of class 2 graphs, Utilitas Mathematica 53 (1998) 243-253.
• R. E. L. Aldred, M. N. Ellingham, R. L. Hemminger and P. Jipsen, P_3-isomorphisms for graphs, J. Graph Theory 26 (1997) 35-51. doi:10.1002/(SICI)1097-0118(199709)26:1<35::AID-JGT5>3.0.CO;2-I
• R. E. L. Aldred, M. N. Ellingham, R. L. Hemminger and D. A. Holton, Cycles in quasi-4-connected graphs, Australasian J. Combinatorics 15 (1997), 37-46.
• M. N. Ellingham and Luis Goddyn, List edge colourings of some 1-factorable multigraphs, Combinatorica 16 (1996) 343-352. doi:10.1007/BF01261320
• M. N. Ellingham, Spanning paths, cycles, trees and walks for graphs on surfaces, Proceedings of the Special Session in Graph Theory at the Amer. Math. Soc. conference, San Francisco, January 1995, Congressus Numerantium 115 (1996) 55-90. PDF preprint (same as journal version).
• M. N. Ellingham, Vertex-switching reconstruction and folded cubes, J. Combinatorial Theory Series B 66 (1996) 361-364. doi:10.1006/jctb.1996.0027
• Richard Brunet, Mark N. Ellingham, Zhicheng Gao, Alice Metzlar and R. Bruce Richter, Spanning planar subgraphs of graphs in the torus and Klein bottle, J. Combinatorial Theory Series B 65 (1995) 7-22. doi:10.1006/jctb.1995.1041
• M. N. Ellingham, R. L. Hemminger and Kathryn E. Johnson, Contractible edges in longest cycles in nonhamiltonian graphs, Discrete Math. 133 (1994) 89-98. doi:10.1016/0012-365X(94)90018-3
• M. N. Ellingham and Zhicheng Gao, Spanning trees in locally planar triangulations, J. Combinatorial Theory Series B 61 (1994) 178-198. doi:10.1006/jctb.1994.1043
• M. N. Ellingham, Basic subgraphs and graph spectra, Australasian J. Combinatorics 8 (1993) 247-265. Journal version.
• M. N. Ellingham, Sum graphs from trees, Ars Combinatoria 35 (1993) 335-349. Journal scan.
• S. R. Campbell, M. N. Ellingham and Gordon F. Royle, A characterisation of well-covered cubic graphs, J. Combinatorial Math. and Combinatorial Computing 13 (1993) 193-212. Journal scan.
• M. N. Ellingham and Gordon F. Royle, Vertex-switching reconstruction of subgraph numbers and triangle-free graphs, J. Combinatorial Theory Series B 54 (1992) 167-177. doi:10.1016/0095-8956(92)90048-3
• M. N. Ellingham, Vertex-switching, isomorphism and pseudosimilarity, J. Graph Theory 15 (1991) 563-572. doi:10.1002/jgt.3190150602
• M. N. Ellingham, L. Pyber and Xingxing Yu, Claw-free graphs are edge reconstructible, J. Graph Theory 12 (1988) 445-451. doi:10.1002/jgt.3190120317
• M. N. Ellingham, Recent progress in edge reconstruction, Proc. 17th Manitoba Conf. on Numerical Math. and Computing, Winnipeg, 1987, Congressus Numerantium 62 (1988) 3-20. Journal scan.
• M. N. Ellingham, Isomorphic factorization of regular graphs of even degree, J. Australian Math. Soc. (Series A) 44 (1988) 402-420.
• M. N. Ellingham, Isomorphic factorization of r-regular graphs into r parts, Discrete Math. 69 (1988) 19-34. doi:10.1016/0012-365X(88)90174-4
• M. N. Ellingham and N. C. Wormald, Isomorphic factorization of regular graphs and 3-regular multigraphs, J. London Math. Soc. (2) 37 (1988) 14-24. doi:10.1112/jlms/s2-37.121.14
• Wendy Myrvold, M. N. Ellingham and D. G. Hoffman, Bidegreed graphs are edge reconstructible, J. Graph Theory 11 (1987) 281-302. doi:10.1002/jgt.3190110304
• M. N. Ellingham and Y. Caro, Uniqueness of impartial edge-colourings, Ars Combinatoria 22 (1986) 59-71. Journal scan.
• I. Krasikov, M. N. Ellingham and Wendy Myrvold, Legitimate number decks for trees, Ars Combinatoria 21 (1986) 15-17.
• M. N. Ellingham, Petersen subdivisions in some regular graphs, Proc. 15th Southeastern Conf. on Combinatorics, Graph Theory and Computing, Baton Rouge, 1984, Congressus Numerantium 44 (1984) 33-40. Journal scan.
• M. N. Ellingham, D. A. Holton and C. H. C. Little, Cycles through ten vertices in 3-connected cubic graphs, Combinatorica 4 (1984) 265-273. doi:10.1007/BF02579136
• M. N. Ellingham and J. D. Horton, Non-hamiltonian 3-connected cubic bipartite graphs, J. Combinatorial Theory Series B 34 (1983) 350-353. doi:10.1016/0095-8956(83)90046-1
• M. N. Ellingham, The asymptotic connectivity of labelled coloured regular bipartite graphs, Combinatorics X, Proc. 10th Australian Conf. on Combinatorial Mathematics, Adelaide, 1982, Lecture Notes in Math. 1036, Springer, Berlin, 1983, 177-188. doi:10.1007/BFb0071518.
• M. N. Ellingham, Constructing certain cubic graphs, Combinatorics IX, Proc. 9th Australian Conf. on Combinatorial Mathematics, Brisbane, 1981, Lecture Notes in Math. 952, Springer, Berlin, 1982, 252-274. doi:10.1007/BFb0061983.

Theses

• M. N. Ellingham, Isomorphic Factorizations of Regular Graphs, thesis for Doctor of Philosophy, University of Waterloo, 1986.
• M. N. Ellingham, Cycles in 3-connected Cubic Graphs, thesis for Master of Science, University of Melbourne, 1982.