In the works: a book “Exploring Graphs via Harmonic Morphisms”

Posted on 2025/10/07 by wdjoyner

Caroline Melles and I have been working for some years on a 2-volume book in graph theory which investigates harmonic morphisms. These are, roughly speaking, mappings from one graph to another that preserve locally harmonic functions on these graphs. Therefore, this topic fits into the general framework of harmonic analysis on graphs.

This post only concerns the first volume. The intent here is to mention some of the types of results we obtain. Of course, by no means is it intended to be a complete description.

The second volume will be summarized in a separate post.

Graphs in our book are unweighted and, unless stated otherwise, have no loops or multiple edges. The basic idea is this: in chapter 2 we classify harmonic morphisms using a criteria expressed as a matrix identity. For various graph-theoretical constructions (such as edge deletion or join or a graph product or …) that can be performed on a given graph Gamma, we pick a graph morphism associated to the construction (such as sending a vertex in the constructed graph to the given graph). That morphism is associated to a matrix (which we called the vertex map matrix in chapter 3 of our earlier book, Adventures in Graph Theory). When this matrix satisfies the above-mentioned matrix criteria then the associated morphism is harmonic.

Chapter 1 is on Graph Morphisms.

This chapter is devoted to background on graph morphisms and some of the methods we use to study them.

Roughly speaking, a morphism is a mapping between graphs that preserves incidence structure. After defining horizontal and vertical edges, vertical multiplicities, local horizontal multiplicities, it recalls well-known graph families like cycle graphs, path graphs, and complete graphs.
There are a few very useful degree identities. First, there is a fundamental formula relating vertex degrees to multiplicities under morphisms. There is also a formula for the degree
of the morphism in terms of vertical multiplicities and local horizontal multiplicities.
A topic threading through the book is that of matrix-theoretic methods. This first chapter introduces vertex map matrices and edge map matrices that encode morphisms. After establishing key matrix identities and products, reviews adjacency matrices and their spectra, with detailed analysis of cycle graph eigenvalues using Chebyshev polynomials and complex roots of unity.
It recalls signed and unsigned incidence matrices, with and without edge orientations, and establishes the fundamental Graph Homomorphism Identity relating incidence matrices to morphism matrices,
introduces Laplacian matrices as differences of degree and adjacency matrices, connecting to the incidence matrix framework.
Introduced graph blowup morphisms via a blowup construction where vertices are replaced by independent sets, creating natural homomorphisms with specific structural properties.
Some functorial properties of graph morphisms are established, such as how morphisms behave under graph constructions like subdivisions, smoothing, deletions, and substitutions.
The chapter ends with exercises and a chapter summary.

Chapter 2 on Harmonic Morphisms

This chapter is devoted to the basics of harmonic morphisms.

Introduces the core definition: a graph morphism is harmonic if local horizontal multiplicities are constant across edges incident to each vertex’s image.
Cycle space and cocycle space – Develops the algebraic framework using homology and cohomology of graphs. Covers Urakawa’s theorem on pullbacks of harmonic 1-forms and Baker-Norin results on divisors and Jacobians.
Matrix-theoretic methods – Establishes the fundamental matrix characterization: a morphism is harmonic iff there exists a diagonal multiplicity matrix satisfying specific adjacency matrix identities. Proves equivalence with an analogous Laplacian matrix identity and an analogous incidence matrix criteria.
The Riemann-Hurwitz formula – Presents the graph-theoretic analogue relating genera of graphs via harmonic morphisms, with matrix proof and applications to regular graphs.
Some functorial consequences – Demonstrates how harmonic morphisms interact with graph constructions like subdivision, edge substitution, leaf addition, and deletion. Shows these
operations preserve harmonicity under appropriate conditions.
The chapter ends with exercises and a chapter summary.

All harmonic morphisms from this graph to C4 are covers.

Fundamental Problem: Given a graph Gamma1, for which graphs Gamma2 is there a non-trivial harmonic morphism phi from Gamma2 to Gamma1?

Follow-up question: Can the number of such phi be counted?

Chapter 3 on Counting Problems

This chapter looks at various families, such as the path graphs. What is especially remarkable is that, as we will see, the problem of counting harmonic morphisms often boils down to solving certain recurrance relations, some of which arose (in a completely different context of course) in
the work of medieval mathematicians, both in Europe and in India.

Regarding harmonic morphisms between path graphs, we show how to construct and count the harmonic morphisms from longer path graphs to shorter ones.
Regarding harmonic morphisms between cycle graphs, we show how to construct and count the harmonic morphisms from larger cycle graphs (when they exist) to smaller ones. It turns out all such harmonic morphisms are necessarily covers.
Regarding harmonic morphisms between complete graphs, we show how to construct and count the harmonic morphisms from larger complete graphs (when they exist) to smaller ones.
Harmonic morphisms to P2 (arising from the Baker-Norin Theorem) can be counted.
Harmonic morphisms to P3 (the path graph with only 3 vertices) can be counted in special cases.
There are lots of open questions, such as which trees have a harmonic morphism to P3.
The chapter ends with exercises and a chapter summary.

Chapter 4 on Harmonic Quotient Morphisms

This chapter studies quotient graphs arising from group actions and from vertex partitions.

Quotient graphs from group actions. Harmonic actions and transitive actions are studied separately.
Quotient graphs from paritions. Orbit partitions and equitable partitions are studied.
As a nice application of harmonic morphisms with particularly nice structural properties, we consider multicovers and blowup graphs.
The last section provides explicit formulas for the eigenvalue spectra of harmonic blowups of bipartite graphs, connecting the eigenvalues of the source and target graphs through the blowup parameters. The main result is the Godsil-McKay Theorem.
The chapter ends with exercises and a chapter summary.

Chapter 5 on Graph Morphisms and Graph Products

Roughly speaking, a graph product of Gamma1 with Gamma2 is a graph Gamma3 = (V3, E3), where V3 = V1 x V2 is the Cartesian product and there is a rule for the edges E3 based on some conditions on the vertices. The graph products considered in this book are the disjunctive, Cartesian, tensor, lexicographic, and the strong products.

The most basic questions one wants answered are these:
is the projection pr1 : Gamma1 x Gamma2 to Gamma1 harmonic, and
is the projection pr2 : Gamma1 x Gamma2 to Gamma2 harmonic?
If they do turn out to be harmonic morphisms, we also want to know the vertical and horizontal multiplicities as well. If they do not turn out to be harmonic morphisms, we also want (if possible) to establish conditions on the graphs under which the projections are harmonic.

However, we want to not only consider products of graphs but also products of morphisms.
In this case, the most basic question one wants answered is this:
Given harmonic morphisms phi : Gamma2 to Gamma1 and phi’ : Gamma2′ to Gamma1′, is the
product phi x phi’ harmonic?

For example, we show that projection morphisms from tensor products are always harmonic with explicit horizontal multiplicity formulas.
Moreover, we prove that the tensor product of harmonic morphisms (without vertical edges) yields a harmonic morphism with horizontal multiplicity matrix given by the Kronecker product of the original multiplicity matrices.
If Gamma x Gamma’ is a lexicographical product then the projection onto the first factor, pr1, is a harmonic morphism. However, the projection onto the second factor is not in general.
We establish a connection between the balanced blowup graph and a lexicographical product. One corollary of this connection is that the blowdown graph agrees with the first projection of the product, so is a harmonic morphism.

Chapter 6 on More Products and Constructions

This chapter studies graph morphisms associated to Cartesian/strong/disjunctive products of graphs as well as joins and NEPS graphs.
For example, we show that projection morphisms from Cartesian products or from strong products are always harmonic with explicit horizontal multiplicity formulas.
Roughly speaking, one of the results states:
Given two m-quasi-multicovers phi from Gamma2 to Gamma1 and phi’ from Gamma2′ to Gamma1′, the Cartesian product phi x phi’ is also an m-quasi-multicover (hence harmonic).
Another result, roughly speaking, states:
Given two harmonic morphisms phi from Gamma2 to Gamma1 and phi’ from Gamma2′ to Gamma1′, the
strong product phi x phi’ is also harmonic.
Can one classify the graphs for which the disjunctive product projections pr1 or pr2 are graph morphisms?
For example, we show that if phi from Gamma2 to Gamma1 and phi’ from Gamma2′ to Gamma1′ are graph morphisms, then the associated product map from Gamma2 x Gamma2′ to Gamma1 x Gamma1′ (where x is the disjunctive product) is, in general, not a graph morphism.
Given two harmonic morphisms phi from Gamma2 to Gamma1 and phi’ from Gamma2′ to Gamma1′, the join morphism phi wedge phi’ is harmonic if and only if a certain technical condition is true.
A theorem due to Urakawa states that projection morphisms from a NEPS graph to one
of its factors are always harmonic. Moreover, we give explicit horizontal multiplicity formulas.
The chapter ends with exercises and a chapter summary.

Computations are supported throughout using SageMath and Mathematica. The plan is the publish the volume with Birkhauser. We thank the editors there, especially John Benedetto, for their encouragement and guidance.

The mathematician and the Pope

Posted on 2025/08/21 by wdjoyner

Acknowledgement: This could not have been written without the helpful conversations and correspondences with these brilliant scholars: Edray Goins (Pomoma), John Stigall (Howard), Nathan Alexander (Howard), and Susan Kelly (Univ Wisconsin, retired). Also, I thank the librarians at the Catholic University of America for their help. I’m deeply indebted to them for sharing their knowledge about Haynes’ life and work and philosophy, but if there are mistakes, and I’m sure there are, they are my responsibility alone.

This is a non-technical (I promise!) introduction to the life and work of Euphemia Haynes. She’s a fascinating character known not just for her pure mathematics PhD thesis earned at the age of 53, but for her extraordinary devotion to improving mathematics education for everyone, as well as her service to many charities, especially those related to the Catholic Church.

At the time, the prestigious Papal Decoration of Honor medal, the Pro Ecclesia et Pontifice, was the top award for non-clergy (in particular, all women) bestowed by the Pope. That papal recognition was given to Haynes by Pope John XXIII, when she was almost 70. In fact, hers was the only Pro Ecclesia et Pontifice medal bestowed by the Pope to anyone during his entire tenure.

This is an introduction to her life’s journey.

Upbringing

Born Martha Euphemia Lofton in Washington D.C. on September 11, 1890, Euphemia preferred using her middle name.

Her father, Dr William Lofton, was a dentist while her mother Lavinia was very active in her church and later became an elementary school teacher in the D.C. school district. According to saved correspondence, the family lived on 17th Street and attended, until Euphemia was in her 20s, St Augustine’s which was a few blocks away. Lavinia and Euphemia and Joseph were part of the church choir for many years. Indeed, Lavinia was the organist for the junior choir since Euphemia was a baby.

This familial foundation within the Catholic community likely instilled in Euphemia her values of service, justice, and community engagement.

Education

Lavinia Lofton started teaching in the DC public schools in the fall of 1901 (when Euphemia was 11, as a kindergarten assistant. She was permanently appointed teacher in the DC school system a few years later in the summer of 1903.

Inspired no doubt by her mother, Euphemia’s educational journey was marked by consistent excellence. In fact, she distinguished herself early, graduating as valedictorian from M Street High School in 1907.

Euphemia Lofton began her own teaching career in the DC elementary school system in the fall of 1909. She taught there until the summer of 1912. Then she left for Smith College, where she earned an undergraduate mathematics major (and psychology minor) in 1914. During this time, the letters from her fiance Harold Haynes discuss his plans to visit her, as well as keeping her up to date on various family and business matters in DC. Upon graduation, she immediately returned to DC and started teaching in the high school system in the fall of 1914.

She taught in the Miner Normal School and various local high schools, such as Dunbar, until 1930. At that point she began teaching at the Miner Teachers College (later assimilated with others to become the University of the District of Columbia). As an early indication of her extraordinary administrative talents, Euphemia quickly founded and established the mathematics department at Miner as well.

Marriage

In 1917 she married Harold Appo Haynes, a teacher like herself. The couple had no children. He was a childhood friend and, based on saved letters between he and Euphemia, a source of constant encouragement and strength for her. Harold had a EE degree from the University of Pennsylvania in 1910, and later earned a masters in education from the University of Chicago in 1930, and a doctorate in education from New York University in 1946.

Besides Euphemia’s promotion to teach at the college level, another significant event occurred in 1930. In that year, Euphemia obtained a Master’s degree in education from the University of Chicago (with her husband Harold).

Master’s thesis

Euphemia’s thesis was a significant piece of scholarship. In it, she discussed test validity and student assessment methods. With the goal to trace the evolution of testing in elementary and secondary school mathematics from 1900 to 1930, she focused on the main mathematics subjects arithmetic, algebra, and plane geometry. She surveyed published education literature, analyzed actual test instruments in those subjects, and summarized reports by educators and administrators on their own test development.

In the early 1900s, teachers gave a large group of students the same problem and compared how they did, without a grading key or separation into different skill metrics. In her thesis she notes that educators since those early 1900s started moving away from subjective grading to data-driven evaluation. Tests need to focus objectively on specific abilities. Tests moved from general surveys to fine-grained skill analysis. Indeed, by the 1910s–1920s, grade school tests measured discrete skills within core mathematics subjects. Testing evolved as a tool for diagnosis, curriculum evaluation, and teacher development. She also notes the progression toward standardized tests and its use for diagnosing student challenges.

In fact, after retiring from teaching she because president of the DC Board of Education (the first woman to hold that office). By that point she had grown to be an extremely gifted administrator with a single-minded focus on service to both education and her church. The timing of her presidency, following the 1954 Brown v. Board decision and amidst ongoing civil rights litigation,positioned her to directly implement and enforce desegregation and equity policies. Indeed, it was during her term as president that the track system was eliminated. (For further details, see the discussion of the 1967 Hobson v Hansen District Court case in [KSZ14]).

Volunteer service

Here we mention just a few of the many volunteer efforts Euphemia Haynes generously devoted her time to.

A common thread throughout her life was her commitment to social justice and her leadership in various Catholic organizations.

She co-founded the Catholic Interracial Council of the District of Columbia, an organization she helped establish to promote racial harmony and justice within the Church and broader community. These Catholic Interracial Councils, which united under a national umbrella in 1959-1960, were founded with the explicit aim of bridging racial divides between White and Black populations. The D.C. Council, for instance, played a vital role in coordinating Catholic participation in significant civil rights events.

Haynes also held a significant leadership position as the first vice president of the Archdiocesan Council of Catholic Women, which focused on education, social justice, and assisting immigrants. She later served as president of the local chapter of that Council.

After retiring from teaching in 1959, she didn’t stop working but served others through organizations such as

the AAUW (American Association of University Women),
the Committee of International Social Welfare,
the Executive Committee of the National Social Welfare Assembly,
the D.C. Health and Welfare Council,
the USO,
the Urban League,
the NAACP, and
the League of Women Voters,

to name a few. Her unwavering commitment to social justice was fueled by the Catholic moral imperative to combat racism.

Her involvement with the Catholic Interracial Council and her broader civil rights work exemplify how Catholic social teaching provided a moral framework for her and other social activists during the Civil Rights era. The Church’s evolving stance on racial justice provided a powerful moral authority and a network (such as the Catholic Interracial Council and the Archdiocesan Council of Catholic Women) through which individuals like Haynes could actively pursue desegregation and equality. Her life demonstrates the practical application of religious principles to pressing social issues, showcasing how faith communities were critical sites for civil rights organizing and advocacy.

PhD thesis

Haynes earned her PhD from Catholic University of America (CUA) in 1943. The thesis topic itself is quite technical, to say nothing of the methods and proofs in the thesis itself. Just to understand the setup for the problem she solved in her thesis requires, at a minimum, knowing differential calculus.

In essence, Haynes’ thesis delves into the core of enumerative geometry, a field concerned with counting geometric objects satisfying specific conditions. For example, since the time of the ancient Greeks, mathematicians have known of the Problem of Apollonius: what is the number of circles tangent to three circles in general position? (It turns out the answer is 8.) Euphemia’s problem was in a similar spirit but was of course much harder and, as pointed out, even quite technical to state. None-the-less, her work is rooted in “synthetic” methods from the 1800s emphasizing geometric constructions and reasoning without explicit reliance on algebraic calculations. One of her innovations was to make extensive use of those algebraic calculations that the synthetic method was designed to avoid! In some sense, she solved her thesis problem by first reformulating it in a more complicated mathematical framework, then she worked out the solution.

It may be worth noting that after the 1940s, the methods she used were virtually abandoned for a direct algebraic approach, using machinery borrowed from the relatively recent methods of commutative algebra. For a few more technical details are her thesis see my earlier post “Remarks on …“, also available on this blog.

By the way, she was the first Black woman to ever earn a PhD in mathematics anywhere in the United States. She never requested recognition for this achievement. Indeed, it was over 50 years later when historians of mathematics recognized it was actually her and not someone else!

Unassuming but determined, Euphemia immediately put her understanding of advanced mathematics to work, inspiring not only students in the classroom, but also teachers. In a 1945 address to a meeting of DC mathematics teachers, Euphemia spoke about the unifying nature of what she called symbolic logic. Just as the physicist studies the natural world using rocks, plants, and other physical materials, the mathematician works within the world of logic. She explained that, instead of stones or chemicals, the ”tools” of the mathematician are facts, ideas, relationships, and implications. The abstract objects of logic are the raw materials of advanced mathematics, shaping the universe in which mathematicians explore and create.

Boiled down to its essence, her message to the mathematics teachers in the audience was: Through your service, you are teaching your students to better understand the world around them.

She achieved many academic awards in her life for her service. Another kind of award was bestowed on her from the Catholic Church.

The Pro Ecclesia et Pontifice medal

Just shy of 70 years old, in 1959 Euphemia Lofton Haynes was awarded the Papal Medal, Pro Ecclesia et Pontifice, by Pope John XXIII. This recognized her “outstanding valour and bravery on behalf of the Church and Society,” as well as her extraordinary services to the Church while maintaining fidelity to God and to the Pope. This Papal Decoration of Honor was a powerful affirmation of Euphemia Haynes’s entire life — her academic, professional, and civil rights endeavors. They were expressions of her deep faith and unwavering service to humanity. It’s an appreciation from the Catholic Church for her professional accomplishments in education, including founding departments and teaching for decades, her direct, hands-on service to the community, especially to Catholic students and teachers.

Her life lesson

Euphemia Haynes showed us that mathematics is not just about numbers. For her, it’s also about perseverance, leadership, and service. She broke barriers in higher education, stood firm in her beliefs, and used her talents to uplift others. Her life is a reminder that your passion — whether in math or something else — can connect to something larger than yourself. You don’t have to choose between mathematical expertise and helping others. As Euphemia Haynes showed us, you can do both.

References

[Ha30] E. L. Haynes, The Historical Development of Tests in Elementary and Secondary Mathematics, Masters Thesis, University of Chicago, 1930. pdf: click here

[Ha43] ——, Determination of Sets of Independent Conditions Characterizing Certain Special Cases of Symmetric Correspondences, Doctoral Thesis (advisor Aubrey Landry), The Catholic University of America, Washington DC, 1943. pdf: click here

[Ha45] —-, Mathematics – symbolic logics (typewritten and hand-written notes for a talk on the nature of advanced mathematics), address to Teachers of Mathematics in Jr. and Sr. High Schools (1945), Washington DC. (Available from the collected works of Euphemia Haynes at Catholic University of America.)

[KSZ14] S. Kelly, C. Shimmers, K. Zoroufy, Euphemia Lofton Haynes: Bringing education closer to the “goal of Perfection’‘, available online at the url arxiv.org/abs/1703.00944.

Mathematics PhD students of Aubrey Edward Landry

Posted on 2025/04/26 by wdjoyner

Based on information primarily sourced from the Mathematics Genealogy Project and university records, here are the Ph.D. students in Mathematics who graduated from The Catholic University of America between 1910 and 1950 under the advisement of Professor Aubrey Edward Landry:

1. Sister Mary Gervase Kelley (1917)*
Thesis Title: On the Cardioids Fulfilling Certain Assigned Conditions
2. Joseph Nelson Rice (1917)*
Thesis Title: On the In-and-Circumscribed Triangles of the Plane Rational Quartic Curve
3. Louis Antoine De Cleene (1927)*
Thesis Title: On Triangles Circumscribed about a Conic and Inscribed in a Cubic Curve
4. Frank Engelbert Smith (1928)*
Thesis Title: The Triangles In and-Circumscribed to the Triangular-Symmetric Rational Quartic
5. James Norman Eastham (1931)*
Thesis Title: The Triangles In-and-circumscribed to the Tacnodal Rational Quartic Curve with Residual Crunode
6. Sister Marie Cecilia Mangold (1929)*
Thesis Title: The Loci Described by the Vertices of Singly Infinite Systems of Triangles Circumscribed about a Fixed Conic
7. Sister Leonarda Burke (1931)*
Thesis Title: On a case of the triangles in-and-circumscribed to a rational quartic curve with a line of symmetry
8. Sister Mary de Lellis Gough (1931)
Thesis Title: On the Condition for the Existence of Triangles In-and-Circumscribed to Certain Types of Rational Quartic Curve and Having a Common Side
9. Sister Charles Mary Morrison (1931)*
Thesis Title: The Triangles In-and-Circumscribed to the Biflecnodal Rational Quartic
10. Sister Mary Felice Vaudreuil (1931)*
Thesis Title: Two Correspondences Determined by the Tangents to a Rational Cuspidal Quartic with a Line of Symmetry
11. Sister Mary Domitilla Thuener (1932)*
Thesis Title: On the Number and Reality of the Self-Symmetric Quadrilaterals In-and-Circumscribed to the Triangular-Symmetric Rational Quartic
12. Sister Mary Nicholas Arnoldy (1932)*
Thesis Title: The Reality of the Double Tangents of the Rational Symmetric Quartic Curve
13. Sister Mary Helen Sullivan (1934)*
Thesis Title: The Number and Reality of the Non-Self-Symmetric Quadrilaterals In-and-Circumscribed to the Rational Unicuspidal Quartic with a Line of Symmetry
14. Sister Mary Laetitia Hill (1935)*
Thesis Title: The Number and Reality of Quadrilaterals In-and-Circumscribed to a Rational Unicuspidal Quartic with Real Tangents from the Cusp
15. Sister Mary Henrietta Reilly (1936)*
Thesis Title: Self-Symmetric Quadrilaterals In-and-Circumscribed to the Plane Rational Quartic Curve with a Line of Symmetry
16. Sister Mary Charlotte Fowler (1937)*
Thesis Title: The discriminant of the sextic of double point parameters of the plane rational quartic curve
17. Sister Catherine Francis Galvin (1938)*
Thesis Title: Two Geometrical Representations of the Symmetric Correspondence C(N,N) with Their Interrelations
18. Euphemia Lofton Haynes (1943)*
Thesis Title: Determination of Sets of Independent Conditions Characterizing Certain Special Cases of Symmetric Correspondences
19. Brother Cyprian John McNamara (1948)*
Thesis Title: The Reality of the Double Tangents of the Rational Bicircular Symmetric Quartic

Note, most of these are nuns. Other than Brother McNamara, Landry advised de Cleene (1927) who had received his Holy Orders 8 years earlier.

Landry had three male “civilian” students (Rice, 1917, Smith 1928, Eastham, 1931) and one female “civilian” student (Haynes, 1943). Rice was later hired full time at Catholic University. Eastham was soon hired to teach at Nazareth College. Haynes, 16 years later, was awarded the highest award the Pope (Pope John XXIII) could give to a woman: the Pro Ecclesia et Pontifice medal.

An asterisk next to a name means that I’ve obtain the PhD by inter-library loan (usually from CUA). If there are any additions or missing students, please let me know!

Remarks on the 1943 PhD thesis of E. Haynes

Posted on 2024/05/04 by wdjoyner

Euphemia Haynes was a trailblazer as the first African-American woman to earn a doctorate in mathematics. The Catholic University of America holds a copy of her thesis, entitled “The Determination of Sets of Independent Conditions Characterizing Certain Special Cases of Symmetric Correspondences”, in their archives.

A short biography: Euphemia Lofton daughter of Dr William Lofton, a dentist, and Lavinia Day Lofton, a kindergarten teacher. She was the valedictorian of M Street High School in 1907 and then graduated from (what is now known as) University of the District of Columbia with distinction and a degree in education in 1909. She was a mathematics major at Smith College, which she graduated from in 1914. She married Harold Appo Haynes, a teacher in 1917 and earned her master’s degree in education from the University of Chicago in 1930. In 1943 she was awarded her PhD from The Catholic University of America, advised by Professor Aubrey E. Landry. An excellent, more detailed biography can be found at [KSZ] (see also http://www.math.buffalo.edu/mad/PEEPS/haynes.euphemia.lofton.html).

More of her biography is given in the post The Mathematician and the Pope, also available on this blog.

In this blog post, we merely try to explain her title. What is a “symmetric correspondence”?

We refer to Dolgachev’s notes [Do14], section 5.5: A correspondence of degree d between nonsingular curves X and Y is a non-constant morphism $T:X\to Y^{(d)}$ to the d-th symmetric product $Y^{(d)}$ of $Y$. Its graph is denoted $\Gamma_T\subset X\times Y$ . The projection $\Gamma_T\to X$ is a finite map of degree $d$, while the projection $\Gamma_T\to Y$ is a finite map of degree e, say. It defines a correspondence $Y\to X^{(e)}$ denoted by $T^{-1}$ , called the inverse correspondence. Its graph $\Gamma_{T^{-1}}\subset Y\times X$ is the image of $\Gamma_T$ under the swap $X\times Y\to Y\times X$ . If d is the degree of T and e is the degree of $T^{-1}$ , we say that $T$ is a correspondence of type (d, e). This correspondence is symmetric if $T = T^{-1}$ .

Very roughly speaking, in her thesis, Haynes looks at various special cases of curves and in these cases she derives (technically defined) conditions that characterize the types of symmetric correspondences that arise in those cases.

While a scan of her thesis is archived at Catholic University, I have typed up her thesis in latex. For a digital copy, just email me (wdjoyner@gmail.com).

References

[Do14] I. Dolgachev, Classical Algebraic Geometry: a modern view, Cambridge Univ. Press, 2012.

(at https://mathweb.ucsd.edu/~eizadi/207A-14/CAG.pdf)

[KSZ17] Susan Kelly, Carly Shinners, Katherine Zoroufy, “Euphemia Lofton Haynes: Bringing Education Closer to the “Goal of Perfection“, preprint, 2017 (available at https://arxiv.org/abs/1703.00944). A version of this paper was also published in the Notices of the American Mathematics Society.

Harmonic quotients of regular graphs – examples

Posted on 2023/01/06 by wdjoyner

Caroline Melles and I have written a preprint that collects numerous examples of harmonic quotient morphisms $\phi : \Gamma_2 \to \Gamma_1$ , where $\Gamma_1=\Gamma_2/G$ is a quotient graph obtained from some subgroup $G \subset Aut(\Gamma_2)$ . The examples are for graphs having a small number of vertices (no more than 12). For the most part, we also focused on regular graphs with small degree (no more than 5). They were all computed using SageMath and a module of special purpose Python functions I’ve written (available on request). I’ve not counted, but the number of examples is relatively large, maybe over one hundred.

I’ll post it to the math arxiv at some point but if you are interested now, here’s a copy: click here for pdf.

Coding Theory and Cryptography

Posted on 2021/10/11 by wdjoyner

This was once posted on my USNA webpage. Since I’ve retired, I’m going to repost it here.

Coding Theory and Cryptography:
From Enigma and Geheimschreiber to Quantum Theory
(David Joyner, ed.) Springer-Verlag, 2000.
ISBN 3-540-66336-3

Summary: These are the proceedings of the “Cryptoday” Conference on Coding Theory, Cryptography, and Number Theory held at the U. S. Naval Academy during October 25-26, 1998. This book concerns elementary and advanced aspects of coding theory and cryptography. The coding theory contributions deal mostly with algebraic coding theory. Some of these papers are expository, whereas others are the result of original research. The emphasis is on geometric Goppa codes, but there is also a paper on codes arising from combinatorial constructions. There are both, historical and mathematical papers on cryptography.
Several of the contributions on cryptography describe the work done by the British and their allies during World War II to crack the German and Japanese ciphers. Some mathematical aspects of the Enigma rotor machine and more recent research on quantum cryptography are described. Moreover, there are two papers concerned with the RSA cryptosystem and related number-theoretic issues.

Chapters

Reminiscences and Reflections of a Codebreaker, by Peter Hilton pdf
FISH and I, by W. T. Tutte pdf
Sturgeon, The FISH BP Never Really Caught, by Frode Weierud, pdf
ENIGMA and PURPLE: How the Allies Broke German and Japanese Codes During the War, by David A. Hatch pdf
The Geheimschreiber Secret, by Lars Ulfving, Frode Weierud pdf
The RSA Public Key Cryptosystem, by William P. Wardlaw pdf
Number Theory and Cryptography (using Maple), by John Cosgrave pdf
A Talk on Quantum Cryptography or How Alice Outwits Eve, by Samuel J. Lomonaco, Jr. pdf
The Rigidity Theorems of Hamada and Ohmori, Revisited, by T. S. Michael pdf
Counting Prime Divisors on Elliptic Curves and Multiplication in Finite Fields, by M. Amin Shokrollahi pdf,
On Cyclic MDS-Codes, by M. Amin Shokrollahi pdf
Computing Roots of Polynomials over Function Fields of Curves, by Shuhong Gao, M. Amin Shokrollahi pdf
Remarks on codes from modular curves: MAPLE applications, by David Joyner and Salahoddin Shokranian, pdf

For more cryptologic history, see the National Cryptologic Museum.

This is now out of print and will not be reprinted (as far as I know). The above pdf files are posted by written permission. I thank Springer-Verlag for this.

Shanks’ SQUFOF according to McMath

Posted on 2021/07/30 by wdjoyner

In 2003, a math major named Steven McMath approached Fred Crabbe and I about directing his Trident thesis. (A Trident is like an honors thesis, but the student gets essentially the whole year to focus on writing the project.) After he graduated, I put a lot of his work online at the USNA website. Of course, I’ve retired since then and the materials were removed. This blog post is simply to try to repost a lot of the materials which arose as part of his thesis (which are, as official works of the US government, all in the public domain; of course, Dan Shanks notes are copyright of his estate and are posted for scholarly use only).

McMath planned to study Dan Shanks‘ SQUFOF method, which he felt could be exploited more than had been so far up to that time (in 2004). This idea had a little bit of a personal connection for me. Dan Shanks was at the University of Maryland during the time (1981-1983) I was a grad student there. While he and I didn’t talk as much as I wish we had, I remember him as friendly guy, looking a lot like the picture below, with his door always open, happy to discuss mathematics.

One of the first things McMath did was to type up the handwritten notes we got (I think) from Hugh Williams and Duncan Buell. A quote from a letter from Buell:

“Dan probably invented SQUFOF in 1975. He had just bought an HP 67 calculator, and the algorithm he invented had the advantages of being very simple to program, so it would fit on the calculator, very powerful as an algorithm when measured against the size of the program, and it factors double precision numbers using single precision arithmetic.“

Here are some papers on this topic (with thanks to Michael Hortmann for the references to Gower’s papers):

David Joyner, Notes on indefinite integral binary quadratic forms with SageMath, preprint 2004. pdf

F. Crabbe, D. Joyner, S. McMath, Continued fractions and Parallel SQUFOF, 2004. arxiv

D. Shanks, Analysis and Improvement of the Continued Fraction Method of Factorization, handwritten notes 1975, typed into latex by McMath 2004. pdf.

D. Shanks, An Attempt to Factor N = 1002742628021, handwritten notes 1975, typed into latex by McMath 2004. pdf.

D. Shanks, SQUFOF notes, handwritten notes 1975, typed into latex by McMath 2004. pdf.

S. McMath, Daniel Shanks’ Square Forms Factorization, 2004 preprint. pdf1, pdf2.

S. McMath, Parallel Integer Factorization Using Quadratic Forms, Trident project, 2004. pdf.

Since that time, many excellent treatments of SQUFOF have been presented. For example, see

J. Gower, S. Wagstaff, Square Form Factorization, Math Comp, 2008. pdf.

J. Gower, Square Form Factorization, PhD Thesis, December 2004. pdf.

Harmonic morphisms from cubic graphs of order 8 to a graph of order 4

Posted on 2020/06/08 by wdjoyner

There are five simple cubic graphs of order 8 (listed here) and there are 6 connected graphs of order 4 (listed here). But before we get started, I have a conjecture.

Let $\Gamma_1$ be a simple graph on n1 vertices, $\Gamma_2$ a simple graph on n2 vertices, and assume there is a harmonic morphism $\phi:\Gamma_1 \to \Gamma_2$ . Call an n1-tuple of “colors” $\{0,1,2,..., n2-1\}$ a harmonic color list (HCL) if it’s attached to a harmonic morphism in the usual way (the ith coordinate is j if $\phi$ sends vertex i of $\Gamma_1$ to vertex j of $\Gamma_2$ ). Let S be the set of all such HCLs. The automorphism group $G_1$ of $\Gamma_1$ acts on S (by permuting coordinates associated to the vertices of $\Gamma_1$ , as does the automorphism group $G_2$ of $\Gamma_2$ (by permuting the “colors” associated to the vertices of $\Gamma_2$ ). These actions commute. Clearly S decomposes as a disjoint union of distinct $G_1\times G_2$ orbits. The conjecture is that there is only one such orbit.

Note: Caroline Melles has disproven this conjecture. Still, the question of the number of orbits is an interesting one, IMHO.

Onto the topic of the post! The 6 connected graphs of order 4 are called P4 (the path graph), D3 (the star graph, also $K_{3,1}$ ), C4 (the cycle graph), K4 (the complete graph), Paw (C3 with a “tail”), and Diamond (K4 but missing an edge). All these terms are used on graphclasses.org. The results below were obtained using SageMath.

We start with the graph $\Gamma_1$ listed 1st on wikipedia’s Table of simple cubic graphs and defined using the sage code sage: Gamma1 = graphs.LCFGraph(8, [2, 2, -2, -2], 2). This graph $\Gamma_1$ has diameter 3, girth 3, and its automorphism group G is generated by (5,6), (1,2), (0,3)(4,7), (0,4)(1,5)(2,6)(3,7), $|G|=16$ . This graph is not vertex transitive. Its characteristic polynomial is $x^8 - 12x^6 - 8x^5 + 38x^4 + 48x^3 - 12x^2 - 40x - 15$ . Its edge connectivity and vertex connectivity are both 2. This graph has no non-trivial harmonic morphisms to D3 or P4 or C4 or Paw. However, there are 48 non-trivial harmonic morphisms to $\Gamma_2=K4$ . For example,
(the automorphism group of K4, ie the symmetric group of degree 4, acts on the colors {0,1,2,3} and produces 24 total plots), and (again, the automorphism group of K4, ie the symmetric group of degree 4, acts on the colors {0,1,2,3} and produces 24 total plots). There are 8 non-trivial harmonic morphisms to $\Gamma_2={\rm Diamond}$ . For example, and Here the automorphism group of K4, ie the symmetric group of degree 4, acts on the colors {0,1,2,3}, while the automorphism group of the graph $\Gamma_1$ acts by permuting some of the coordinates, for example, it can swap the 5th and 6th coordinates.Next, we take for $\Gamma_1$ the graph listed 2nd on wikipedia’s Table of simple cubic graphs and defined using the sage code sage: Gamma1 = graphs.LCFGraph(8, [4, -2, 4, 2], 2). This graph $\Gamma_1$ has diameter 3, girth 3, and its automorphism group G is generated by (1,7)(2,6)(3,5), (0,4)(1,3)(5,7), $|G|=4$ (obviously too small to act transitively on the vertices). Its characteristic polynomial is $x^8 - 12x^6 - 4x^5 + 38x^4 + 16x^3 - 36x^2 - 12x + 9$ , its edge connectivity and vertex connectivity are both 3. This graph has no non-trivial harmonic morphisms to D3 or P4 or C4 or Paw or K4. However, it has 4 non-trivial harmonic morphisms to Diamond. They are:
Let $\Gamma_1$ denote the graph listed 3rd on wikipedia’s Table of simple cubic graphs and defined using the sage code sage: Gamma1 = graphs.LCFGraph(8, [2, 4, -2, 3, 3, 4, -3, -3], 1). This graph $\Gamma_1$ has diameter 2, girth 3, and its automorphism group G is generated by (4,6), (1,2)(3,5), (0,1)(5,7), $|G|=12$ . It does not act transitively on the vertices. Its characteristic polynomial is $x^8 - 12x^6 - 2x^5 + 36x^4 - 31x^2 + 12x$ and its edge connectivity and vertex connectivity are both 3.
This graph has no non-trivial harmonic morphisms to P4 or C4 or Paw or K4 or Diamond. However, it has 6 non-trivial harmonic morphisms to D3, for example,

The automorphism group of D3 (the symmetric group of degree 3) acts by permuting the colors {0,1,2,3} and so yields a total of 6=3! such harmonic color plots.Let $\Gamma_1$ denote the graph listed 4th on wikipedia’s Table of simple cubic graphs and defined using the sage code sage: Gamma1 = graphs.LCFGraph(8, [4, -3, 3, 4], 2). This example is especially interesting. Otherwise known as the “cube graph” $Q_3$ , this graph $\Gamma_1$ has diameter 3, girth 4, and its automorphism group G is generated by ((2,4)(5,7), (1,7)(4,6), (0,1,4,5)(2,3,6,7), $|G|=48$ . It is vertex transitive. Its characteristic polynomial is $x^8 - 12x^6 + 30x^4 - 28x^2 + 9$ and its edge connectivity and vertex connectivity are both 3.
This graph has no non-trivial harmonic morphisms to D3 or P4 or Paw. However, it has 24 non-trivial harmonic morphisms to C4, 24 non-trivial harmonic morphisms to K4, and 24 non-trivial harmonic morphisms to Diamond. An example of a non-trivial harmonic morphism to K4:

A few examples of a non-trivial harmonic morphism to Diamond:
and
A few examples of a non-trivial harmonic morphism to C4:

The automorphism group of C4 acts by permuting the colors {0,1,2,3} cyclically, while the automorphism group G acts by permuting coordinates. These yield more harmonic color plots.

Duursma zeta function of a graph

Posted on 2020/05/28 by wdjoyner

I’m going to start off with two big caveats:

This is not Duursma‘s definition, it’s mine.
I’m not convinced (yet?) that it’s a useful idea to examine such a zeta function.

So that’s your warning – you may be wasting your time reading this!

The Duursma zeta function of a linear block (error-correcting) code is due to Iwan Duursma and is a fascinating object of study. (More precisely, it’s defined for “formal” linear block codes, ie, defined via a weight enumerator polynomial with a suitable MacWilliams-like functional equation.) Sometimes it satisfies an analog of the Riemann hypothesis and sometimes it doesn’t. And sometimes that analog is still an open question.

Duursma zeta function of a code

Before we define the Duursma zeta function of a graph, we introduce the Duursma zeta function of a code.

Let $C$ be an $[n,k,d]_q$ code, ie a linear code over $GF(q)$ of length $n$ , dimension $k$ , and minimum distance $d$ . In general, if $C$ is an $[n,k,d]_q$ -code then we use $[n,k^\perp,d^\perp]_q$ for the parameters of the dual code, $C^\perp$ . It is a consequence of Singleton’s bound that $n+2-d-d^\perp\geq$ , with equality when $C$ is an MDS code. Motivated by analogies with local class field theory, in [Du] Iwan Duursma introduced the (Duursma) zeta function $\zeta=\zeta_C$ :

$\zeta_C(T)=\frac{P(T)}{(1-T)(1-qT)},$
where $P(T)=P_C(T)$ is a polynomial of degree $n+2-d-d^\perp$ , called the zeta polynomial of $C$ . We next sketch the definition of the zeta polynomial.

If $C^\perp$ denotes the dual code of $C$ , with parameters $[n,n-k,d^\perp]$ then the MacWilliams identity relates the weight enumerator $A_{C^\perp}$ of $C^\perp$ to the weight enumerator $A_{C}$ of $C$ :

$A_{C^\perp}(x,y) = |C|^{-1}A_C(x+(q-1)y,x-y).$
A polynomial $P(T)=P_C(T)$ for which

$\frac{(xT+(1-T)y)^n}{(1-T)(1-qT)}P(T)=\dots +\frac{A_C(x,y)-x^n}{q-1}T^{n-d}+\dots \ .$
is a (Duursma) zeta polynomial of $C$ .

Theorem (Duursma): If $C$ be an $[n,k,d]_q$ code with $d\geq 2$ and $d^\perp\geq 2$ then the Duursma zeta polynomial $P=P_C$ exists and is unique.

See the papers of Duursma for interesting properties and conjectures.

Duursma zeta function of a graph

Let $\Gamma=(V,E)$ be a graph having $|V(\Gamma)|$ vertices and $|E(\Gamma)|$ edges. We define the zeta function of $\Gamma$ via the Duursma zeta function of the binary linear code defined by the cycle space of $\Gamma$ .

Theorem (see [DKR], [HB], [JV]): The binary code $B=B_\Gamma$ generated by the rows of the incidence matrix of $\Gamma$ is the cocycle space of $\Gamma$ over $GF(2)$ , and the dual code $B^\perp$ is the cycle space $Z=Z_\Gamma$ of $\Gamma$ :

$B_\Gamma^\perp = Z_\Gamma.$
Moreover,
(a) the length of $B_\Gamma$ is $|E|$ , dimension of $B_\Gamma$ is $|V|-1$ , and the minimum distance of $B_\Gamma$ is the edge-connectivity of $\Gamma$ ,
(b) length of $Z_\Gamma$ is $|E|$ , dimension of $Z_\Gamma$ is $|E|-|V|+1$ , and the minimum distance of $Z_\Gamma$ is the girth of $\Gamma$ .

Call $Z_\Gamma$ the cycle code and $B_\Gamma$ the cocycle code.

Finally, we can introduce the (Duursma) zeta function $\Gamma$ :

$\zeta_\Gamma(T)=\zeta_{Z_\Gamma} =\frac{P(T)}{(1-T)(1-qT)},$
where $P=P_\Gamma=P_{Z_\Gamma}$ is the Duursma polynomial of $\Gamma$ .

Example: Using SageMath, when $\Gamma = W_5$ , the wheel graph on 5 vertices, we have

$P_\Gamma(T) = \frac{2}{7}T^4 + \frac{2}{7}T^3 + \frac{3}{14}T^2 + \frac{1}{7}T + \frac{1}{14}.$
All its zeros are of absolute value $1/\sqrt{2}$ .

References

[Du] I. Duursma, Combinatorics of the two-variable zeta function, in Finite fields and applications, 109–136, Lecture Notes in Comput. Sci., 2948, Springer, Berlin, 2004.

[DKR] P. Dankelmann, J. Key, B. Rodrigues, Codes from incidence matrices of graphs, Designs, Codes and Cryptography 68 (2013) 373-393.

[HB] S. Hakimi and J. Bredeson, Graph theoretic error-correcting codes, IEEE Trans. Info. Theory 14(1968)584-591.

[JV] D. Jungnickel and S. Vanstone, Graphical codes revisited, IEEE Trans. Info. Theory 43(1997)136-146.

Harmonic morphisms to D_3 – examples

Posted on 2020/05/01 by wdjoyner

This post expands on a previous post and gives more examples of harmonic morphisms to the tree $\Gamma_2=D_3$ . This graph is also called a star graph $Star_3$ on 3+1=4 vertices, or the bipartite graph $K_{1,3}$ .
D3-0123

We indicate a harmonic morphism by a vertex coloring. An example of a harmonic morphism can be described in the plot below as follows: $\phi:\Gamma_1\to \Gamma_2=D_3$ sends the red vertices in $\Gamma_1$ to the red vertex of $\Gamma_2=D_3$ (we let 3 be the numerical notation for the color red), the blue vertices in $\Gamma_1$ to the blue vertex of $\Gamma_2=D_3$ (we let 2 be the numerical notation for the color blue), the green vertices in $\Gamma_1$ to the green vertex of $\Gamma_2=D_3$ (we let 1 be the numerical notation for the color green), and the white vertices in $\Gamma_1$ to the white vertex of $\Gamma_2=D_3$ (we let 0 be the numerical notation for the color white).

First, a simple remark about harmonic morphisms in general: roughly speaking, they preserve adjacency. Suppose $\phi:\Gamma_1\to \Gamma_2$ is a harmonic morphism. Let $v,w\in V_1$ be adjacent vertices of $\Gamma_1$ . Then either (a) $\phi(v)=\phi(w)$ and $\phi$ “collapses” the edge (vertical) $(v,w)$ or (b) $\phi(v)\not= \phi(w)$ and the vertices $\phi(v)$ and $\phi(w)$ are adjacent in $\Gamma_2$ . In the particular case of this post (ie, the case of $\Gamma_2=D_3$ ), this remark has the following consequence: since in $D_3$ the green vertex is not adjacent to the blue or red vertex, none of the harmonic colored graphs below can have a green vertex adjacent to a blue or red vertex. In fact, any colored vertex can only be connected to a white vertex or a vertex of like color.

To get the following data, I wrote programs in Python using SageMath.

Example 1: There are only the 4 trivial harmonic morphisms $Star_4 \to D_3$ , plus the “obvious” ones obtained from that below and those induced by permutations of the vertices:
Star4-D3-00321 .

My guess is that the harmonic morphisms $Star_5\to D_3$ can be described in a similar manner. Likewise for the higher $Star_n$ graphs. Given a star graph $\Gamma$ with a harmonic morphism to $D_3$ , a leaf (connected to the center vertex 0) can be added to $\Gamma$ and preserve “harmonicity” if its degree 1 vertex is colored 0. You can try to “collapse” such leafs, without ruining the harmonicity property.

Example 2: For graphs like $\Gamma_1=$
C3LeafLeafLeaf-D3-000321
there are only the 4 trivial harmonic morphisms $\Gamma_1 \to D_3$ , plus the “obvious” ones obtained from that above and those induced by permutations of the vertices with a non-zero color.

Example 2.5: Likewise, for graphs like $\Gamma_1=$
3C3-D3-0332211
there are only the 4 trivial harmonic morphisms $\Gamma_1 \to D_3$ , plus the “obvious” ones obtained from that above and those induced by permutations of the vertices with a non-zero color.

Example 3: This is really a non-example. There are no harmonic morphisms from the (3-dimensional) cube graph (whose vertices are those of the unit cube) to $D_3$ .
More generally, take two copies of a cyclic graph on n vertices, $C_n$ , one hovering over the other. Now, connect each vertex of the top copy to the corresponding vertex of the bottom copy. This is a cubic graph that can be visualized as a “thick” regular polygon. (The cube graph is the case $n=4$ .) I conjecture that there is no harmonic morphism from such a graph to $D_3$ .

Example 4: There are 30 non-trivial harmonic morphisms $\Gamma_1 \to D_3$ for the Peterson graph (the last of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page). Here is an example:
petersen-D3-0330120021
Another interesting fact is that this graph has an automorphism group (isomorphic to the symmetric group on 5 letters) which acts transitively on the vertices.

Example 5: There are 12 non-trivial harmonic morphisms $\Gamma_1=K_{3,3} \to D_3$ for the complete bipartite (“utility”) graph $K_{3,3}$ . They are all obtained from either
K_3_3-D3-321000
or
K_3_3-D3-000231
by permutations of the vertices with a non-zero color (3!+3!=12).

Example 6: There are 6 non-trivial harmonic morphisms $\Gamma_1 \to D_3$ for the cubic graph $\Gamma_1=(V,E)$ , where $V=\{0,1,\dots, 9\}$ and $E = \{(0, 3), (0, 4), (0, 6), (1, 2), (1, 5), (1, 9), (2, 3), (2, 7), (3, 6), (4, 5), (4, 9), (5, 8), (6, 7), (7, 8), (8, 9)\}$ . This graph has diameter 3, girth 3, and edge-connectivity 3. It’s automorphism group is size 4, generated by (5,9) and (1,8)(2,7)(3,6). The harmonic morphisms are all obtained from
random3regular10e-D3-1011031102
by permutations of the vertices with a non-zero color (3!=6). This graph might be hard to visualize but it is isomorphic to the simple cubic graph having LCF notation [−4, 3, 3, 5, −3, −3, 4, 2, 5, −2]:
random3regular10e2
which has a nice picture. This is the ninth of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page.

Example 7: (a) The first of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10f
This graph has diameter 5, automorphism group generated by (7,8), (6,9), (3,4), (2,5), (0,1)(2,6)(3,7)(4,8)(5,9). There are no non-trivial harmonic morphisms $\Gamma_1\to D_3$ .
(b) The second of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10g
This graph has diameter 4, girth 3, automorphism group generated by (7,8), (0,5)(1,2)(6,9). There are no non-trivial harmonic morphisms $\Gamma_1\to D_3$ .
(c) The third of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10h
This graph has diameter 3, girth 3, automorphism group generated by (4,5), (0,1)(8,9), (0,8)(1,9)(2,7)(3,6). There are no non-trivial harmonic morphisms $\Gamma_1\to D_3$ .

Example 8: The fourth of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10i
This graph has diameter 3, girth 3, automorphism group generated by (4,6), (3,5), (1,8)(2,7)(3,4)(5,6), (0,9). There are 12 non-trivial harmonic morphisms $\Gamma_1\to D_3$ . For example,
3regular10i-D3-2220301022
and the remaining (3!=6 total) colorings obtained by permutating the non-zero colors. Another example is
3regular10i-D3-1103020111
and the remaining (3!=6 total) colorings obtained by permutating the non-zero colors.

Example 9: (a) The fifth of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10j
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[2,2,-2,-2,5],2) There are no non-trivial harmonic morphisms $\Gamma_1\to D_3$ .
(b) The sixth of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10k
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[2,3,-2,5,-3],2) There are no non-trivial harmonic morphisms $\Gamma_1\to D_3$ .

Example 10: The seventh of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10l-D3-3330222010
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[2,3,-2,5,-3],2). Its automorphism group is order 12, generated by (1,2)(3,7)(4,6), (0,1)(5,6)(7,9), (0,4)(1,6)(2,5)(3,9). There are 6 non-trivial harmonic morphisms $\Gamma_1\to D_3$ , each obtained from the one above by permuting the non-zero colors.

Example 11: The eighth of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10m
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[5, 3, 5, -4, -3, 5, 2, 5, -2, 4],1). Its automorphism group is order 2, generated by (0,3)(1,4)(2,5)(6,7). There are no non-trivial harmonic morphisms $\Gamma_1\to D_3$ .

Example 12: (a) The tenth (recall the 9th was mentioned above) of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10o
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[3, -3, 5, -3, 2, 4, -2, 5, 3, -4],1). Its automorphism group is order 6, generated by (2,8)(3,9)(4,5), (0,2)(5,6)(7,9). There are no non-trivial harmonic morphisms $\Gamma_1\to D_3$ .
(b) The 11th of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10p
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[-4, 4, 2, 5, -2],2). Its automorphism group is order 4, generated by (0,1)(2,9)(3,8)(4,7)(5,6), (0,5)(1,6)(2,7)(3,8)(4,9). There are no non-trivial harmonic morphisms $\Gamma_1\to D_3$ .
(c) The 12th of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10q
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[5, -2, 2, 4, -2, 5, 2, -4, -2, 2],1). Its automorphism group is order 6, generated by (1,9)(2,8)(3,7)(4,6), (0,4,6)(1,3,8)(2,7,9). There are no non-trivial harmonic morphisms $\Gamma_1\to D_3$ .
(d) The 13th of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10r
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[2, 5, -2, 5, 5],2). Its automorphism group is order 8, generated by (4,8)(5,7), (0,2)(3,9), (0,5)(1,6)(2,7)(3,8)(4,9). There are no non-trivial harmonic morphisms $\Gamma_1\to D_3$ .

Example 13: The 14th of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10s-D3-2033020110
By permuting the non-zero colors, we obtain 3!=6 harmonic morphisms from this one. Another harmonic morphism $\Gamma_1\to D_3$ is depicted as:
3regular10s-D3-0302222201
By permuting the non-zero colors, we obtain 3!=6 harmonic morphisms from this one. And another harmonic morphism $\Gamma_1\to D_3$ is depicted as:
3regular10s-D3-1110302011
By permuting the non-zero colors, we obtain 3!=6 harmonic morphisms from this one. Its SageMath command is Gamma1 = graphs.LCFGraph(10,[5, -3, -3, 3, 3],2). Its automorphism group is order 48, generated by (4,6), (2,8)(3,7), (1,9), (0,2)(3,5), (0,3)(1,4)(2,5)(6,9)(7,8). There are a total of 18=3!+3!+3! non-trivial harmonic morphisms $\Gamma_1\to D_3$ .

Example 14: The 15th of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10t-D3-2033020110
By permuting the non-zero colors, we obtain 3!=6 harmonic morphisms from this one. Its SageMath command is Gamma1 = graphs.LCFGraph(10,[5, -4, 4, -4, 4],2). Its automorphism group is order 8, generated by (2,7)(3,8), (1,9)(2,3)(4,6)(7,8), (0,5)(1,4)(2,3)(6,9)(7,8). There are a total of 6=3! non-trivial harmonic morphisms $\Gamma_1\to D_3$ .

Example 15: (a) The 16th of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10u
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[5, -4, 4, 5, 5],2). Its automorphism group is order 4, generated by (0,3)(1,2)(4,9)(5,8)(6,7), (0,5)(1,6)(2,7)(3,8)(4,9). There are no non-trivial harmonic morphisms $\Gamma_1\to D_3$ .
(b) The 17th of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10v
Its SageMath command is Gamma1 = graphs.LCFGraph(10,[5, 5, -3, 5, 3],2). Its automorphism group is order 20, generated by (2,6)(3,7)(4,8)(5,9), (0,1)(2,5)(3,4)(6,9)(7,8), (0,2)(1,9)(3,5)(6,8). This group acts transitively on the vertices. There are no non-trivial harmonic morphisms $\Gamma_1\to D_3$ .
(c) The 18th of the 19 simple cubic graphs on 10 vertices listed on this wikipedia page is the graph $\Gamma_1$ depicted as:
3regular10w
This is an example of a “thick polygon” graph, already mentioned in Example 3 above. Its SageMath command is Gamma1 = graphs.LCFGraph(10,[-4, 4, -3, 5, 3],2). Its automorphism group is order 20, generated by (2,5)(3,4)(6,9)(7,8), (0,1)(2,6)(3,7)(4,8)(5,9), (0,2)(1,9)(3,6)(4,7)(5,8). This group acts transitively on the vertices. There are no non-trivial harmonic morphisms $\Gamma_1\to D_3$ .
(d) The 19th in the list of 19 is the Petersen graph, already in Example 4 above.

We now consider some examples of the cubic graphs having 12 vertices. According to the House of Graphs there are 109 of these, but we use the list on this wikipedia page.

Example 16: I wrote a SageMath program that looked for harmonic morphisms on a case-by-case basis. If there is no harmonic morphism $\Gamma_1\to D_3$ then, instead of showing a graph, I’ll list the edges (of course, the vertices are 0,1,…,11) and the SageMath command for it.

$\Gamma_1=(V_1,E_1)$ , where $E_1=\{ (0, 1), (0, 2), (0, 11), (1, 2), (1, 6), (2, 3), (3, 4), (3, 5), (4, 5), (4, 6), (5, 6), (7, 8), (7, 9), (7, 11), (8, 9), (8, 10), (9, 10), (10, 11)\}$ .
SageMath command:
V1 = [0,1,2,3,4,5,6,7,8,9,10,11] E1 = [(0, 1), (0, 2), (0, 11), (1, 2), (1, 6), (2, 3), (3, 4), (3, 5), (4, 5), (4, 6), (5, 6), (7, 8), (7, 9), (7, 11), (8, 9), (8, 10), (9, 10), (10, 11)] Gamma1 = Graph([V1,E1])
(Not in LCF notation since it doesn’t have a Hamiltonian cycle.)
$\Gamma_1=(V_1,E_1)$ , where $E_1=\{(0, 1), (0, 6), (0, 11), (1, 2), (1, 3), (2, 3), (2, 5), (3, 4), (4, 5), (4, 6), (5, 6), (7, 8), (7, 9), (7, 11), (8, 9), (8, 10), (9, 10), (10, 11)\}$ .
SageMath command:
V1 = [0,1,2,3,4,5,6,7,8,9,10,11] E1 = [(0, 1), (0, 6), (0, 11), (1, 2), (1, 3), (2, 3), (2, 5), (3, 4), (4, 5), (4, 6), (5, 6), (7, 8), (7, 9), (7, 11), (8, 9), (8, 10), (9, 10), (10, 11)] Gamma1 = Graph([V1,E1])
(Not in LCF notation since it doesn’t have a Hamiltonian cycle.)
$\Gamma_1=(V_1,E_1)$ , where $E_1=\{(0,1),(0,3),(0,11),(1,2),(1,6),(2,3),(2,5),(3,4),(4,5),(4,6),(5,6),(7,8),(7,9),(7,11),(8,9),(8,10),(9,10),(10,11)\}$ .
SageMath command:
V1 = [0,1,2,3,4,5,6,7,8,9,10,11] E1 = [(0,1),(0,3),(0,11),(1,2),(1,6),(2,3),(2,5),(3,4),(4,5),(4,6),(5,6),(7,8),(7,9),(7,11),(8,9),(8,10),(9,10),(10,11)] Gamma1 = Graph([V1,E1])
(Not in LCF notation since it doesn’t have a Hamiltonian cycle.)
This example has 12 non-trivial harmonic morphisms.
SageMath command:
V1 = [0,1,2,3,4,5,6,7,8,9,10,11] E1 = [(0,1),(0,3),(0,11),(1,2),(1,6),(2,3),(2,5),(3,4),(4,5),(4,6),(5,6),(7,8),(7,9),(7,11),(8,9),(8,10),(9,10),(10,11)] Gamma1 = Graph([V1,E1])
(Not in LCF notation since it doesn’t have a Hamiltonian cycle.) We show two such morphisms:

The other non-trivial harmonic morphisms are obtained by permuting the non-zero colors. There are 3!=6 for each graph above, so the total number of harmonic morphisms (including the trivial ones) is 6+6+4=16.
$\Gamma_1=(V_1,E_1)$ , where $E_1=\{(0, 1), (0, 3), (0, 11), (1, 2), (1, 11), (2, 3), (2, 10), (3, 4), (4, 5), (4, 8), (5, 6), (5, 7), (6, 7), (6, 9), (7, 8), (8, 9), (9, 10), (10, 11)\}$ .
SageMath command:
Gamma1 = graphs.LCFGraph(12, [3, -2, -4, -3, 4, 2], 2)
This example has 12 non-trivial harmonic morphisms. $\Gamma_1=(V_1,E_1)$ , where $E_1=\{(0, 1), (0, 3), (0, 11), (1, 2), (1, 11), (2, 3), (2, 10), (3, 4), (4, 5), (4, 7), (5, 6), (5, 8), (6, 7), (6, 9), (7, 8), (8, 9), (9, 10), (10, 11)\}$ . (This only differs by one edge from the one above.)
SageMath command:
Gamma1 = graphs.LCFGraph(12, [3, -2, -4, -3, 3, 3, 3, -3, -3, -3, 4, 2], 1)
We show two such morphisms:

And here is another plot of the last colored graph:

The other non-trivial harmonic morphisms are obtained by permuting the non-zero colors. There are 3!=6 for each graph above, so the total number of harmonic morphisms (including the trivial ones) is 6+6+4=16.
$\Gamma_1=(V_1,E_1)$ , where $E_1=\{(0, 1), (0, 4), (0, 11), (1, 2), (1, 3), (2, 3), (2, 5), (3, 4), (4, 5), (5, 6), (6, 7), (6, 8), (7, 8), (7, 10), (8, 9), (9, 10), (9, 11), (10, 11)\}$ .
SageMath command:
Gamma1 = graphs.LCFGraph(12, [4, 2, 3, -2, -4, -3, 2, 3, -2, 2, -3, -2], 1)
This example has 48 non-trivial harmonic morphisms. $\Gamma_1=(V_1,E_1)$ , where $E_1=\{(0, 1), (0, 3), (0, 11), (1, 2), (1, 4), (2, 3), (2, 5), (3, 4), (4, 5), (5, 6), (6, 7), (6, 9), (7, 8), (7, 10), (8, 9), (8, 11), (9, 10), (10, 11)\}$ .
SageMath command:
Gamma1 = graphs.LCFGraph(12, [3, 3, 3, -3, -3, -3], 2)
This example is also interesting as it has a large number of automorphisms – its automorphism group is size 64, generated by (8,10), (7,9), (2,4), (1,3), (0,5)(1,2)(3,4)(6,11)(7,8)(9,10), (0,6)(1,7)(2,8)(3,9)(4,10)(5,11). Here are examples of some of the harmonic morphisms using vertex-colored graphs:

I think all the other non-trivial harmonic morphisms are obtained by (a) permuting the non-zero colors, or (b) applying a element of the automorphism group of the graph.
(list under construction)