pith. sign in

arxiv: 2605.16224 · v1 · pith:YG5JM7JKnew · submitted 2026-05-15 · 🧮 math.CO

The Facial Common Neighbourhood Graph

Riccardo W. Maffucci This is my paper

Pith reviewed 2026-05-20 16:34 UTC · model grok-4.3

classification 🧮 math.CO
keywords common neighbourhood graphfacial common neighbourhood graphpolyhedraplanaritymaximal planar graphscubic graphsodd facesface length
0
0 comments X

The pith

For cubic polyhedra the common neighbourhood graph is planar only if the odd faces meet specific adjacency rules, while for every other polyhedron it is non-planar.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines the common neighbourhood graph con(G) of a polyhedron G, showing that its planarity is governed by the number and mutual adjacency of odd faces when G is cubic, and that con(G) is always non-planar otherwise. It introduces the facial common neighbourhood graph facecon(G), a spanning subgraph of con(G) that records only common neighbours lying on the same face; this graph coincides with con(G) for cubic polyhedra and generalises the reverse radial graph construction. The work proves that any maximal planar facecon(G) forces every face of G to have length at most 6 and gives an explicit characterisation of all square-faced polyhedra whose facecon(G) is maximal planar.

Core claim

For a 3-connected plane graph G the common neighbourhood graph con(G) is planar if and only if G is cubic and the odd faces of G satisfy a precise adjacency condition; in all other cases con(G) is non-planar. The facial common neighbourhood graph facecon(G) is a spanning subgraph of con(G) whose maximality as a planar triangulation implies that G has no face longer than six edges; all polyhedra of maximum face length four whose facecon(G) realises a maximal planar graph are completely classified and constructed.

What carries the argument

The common neighbourhood graph con(G), whose vertices are those of G and whose edges join any pair sharing a common neighbour, together with its facial restriction facecon(G) that only records pairs whose common neighbour lies on one shared face.

If this is right

  • If facecon(G) is maximal planar then every face of G has length at most 6.
  • All polyhedra of maximum face length 4 whose facecon(G) is maximal planar are explicitly constructed.
  • For cubic polyhedra the planarity status of con(G) is completely determined by the number of odd faces and which pairs of them share an edge.
  • The edge-extremal polyhedra with planar con(G) or facecon(G) are characterised for any fixed number of vertices.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The technical lemma that a maximal planar graph with exactly two odd-degree vertices has those vertices non-adjacent may be useful in other problems involving Eulerian orientations or medial graphs.
  • The facial restriction may yield tractable subcases of neighbourhood-graph problems on non-polyhedral plane graphs.
  • The explicit constructions for square-faced polyhedra suggest a possible enumeration or generating function for all such maximal facecon instances.

Load-bearing premise

The input graph must be a polyhedron, that is, a 3-connected plane graph, so that the notions of faces and common neighbours on a single face are unambiguously defined.

What would settle it

Exhibit a single cubic polyhedron whose odd faces are pairwise non-adjacent yet whose common neighbourhood graph is non-planar.

Figures

Figures reproduced from arXiv: 2605.16224 by Riccardo W. Maffucci.

Figure 1
Figure 1. Figure 1: A non-planar graph G such that con(G) is planar (and 2-connected). Remark 1.4. Our results on classifying polyhedral graphs G where con(G) is planar and their proofs rely on studying the odd faces of G, including how many there are and which ones are adjacent i.e., the vertices and edges of the graph odd(G∗ ). This is reminiscent of [7], where the polyhedral graphs that are Kronecker products of graphs (i.… view at source ↗
Figure 2
Figure 2. Figure 2: A polyhedron G (dashed) and the subgraph G1 of facecon(G) spanned by the dark vertices. Note that b, c have the common neighbour a in G, but there is no face containing a, b, c in G, thus by definition bc ̸∈ E(facecon(G)), whereas bc ∈ E(con(G)). In general for a planar graph G, the graph facecon(G) depends on the plane immersion of G. Moreover, it may contain multiple edges and/or loops, and one may consi… view at source ↗
Figure 3
Figure 3. Figure 3: facecon(G) ≃ facecon(G′ ) ≃ H ∪˙ H, and G ̸≃ G′ . 1.3 A result of independent interest on maximal planar graphs While proving Theorems 1.1 and 1.2, in Section 2 we will establish the following interesting and perhaps surprising result. Lemma 1.7. If a maximal planar graph has exactly two odd vertices, then they are not adjacent. Equivalently, if a cubic polyhedron has exactly two odd faces, then they are n… view at source ↗
Figure 4
Figure 4. Figure 4: Examples of polyhedra G such that facecon(G) is maximal planar. Proposition 1.9. Let G be a polyhedron such that facecon(G) is maximal planar. Then all faces of G have length at most 6. Proposition 1.9 will be proven in Section 5. The complete classification of the polyhedra G such that facecon(G) is maximal planar is probably difficult. Due to Proposition 1.9, we know that every face of G is of length at … view at source ↗
Figure 5
Figure 5. Figure 5: Definition 1.10. Remarkably, the class of polyhedra G of maximum face length 4 and such that facecon(G) is maximal planar admits the following neat construction. Theorem 1.11. Let G be a polyhedron of maximal face length 4. Then facecon(G) is maximal planar if and only if G may be constructed from an initial triangle by iterated applications of the transformations T1, T2, T3 to a non-red triangular face [a… view at source ↗
Figure 6
Figure 6. Figure 6: Lemma 1.7. Only a subgraph of G is shown. The remaining possibility is that degGout (u) is even, thus degGin (u) is odd. Since degGout (u) is even, by the handshaking lemma for Gout, degGout (ui) and degGout (uj ) have the same parity. By minimality of p, odd(Gout) ̸≃ K2, thus degGout (ui) and degGout (uj ) are both even. Since ui , uj have even degree in G and Gout, then they have even degree also in Gin.… view at source ↗
Figure 7
Figure 7. Figure 7: Illustration of Proposition 2.2. in this order (clockwise, say). If we show that ρ is bounded by a cycle, it will follow that every region of G′ is bounded by a cycle, thus G′ is 2-connected. To construct G′ starting from G, we delete u1v1, u2v2, . . . , unvn in turn. At each step, uivi is the common edge of two regions φi = [ui , vi , a1, a2, . . . , aA], A ≥ 1 and φi+1 = [ui , vi , b1, b2, . . . , bB], B… view at source ↗
Figure 8
Figure 8. Figure 8: Construction for Proposition 2.3. (a) G. (b) G ′ . (c) con(G ′ ) = G1 ∪˙ G2. (d) con(G) [PITH_FULL_IMAGE:figures/full_fig_p014_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Illustration of Proposition 2.3. appear in this order along a region ρ, as in Figures 8b and 9b. We write NG(a) = {b, w, x}, NG(b) = {a, y, z}, NG(c) = {d, w′ , x′}, NG(d) = {c, y′ , z′} where in each case the neighbours appear in clockwise order around the vertex. We are also assuming w.l.o.g. that β, γ, δ appear in this clockwise order around α, that b is the clockwise neighbour of a on α, and d the cloc… view at source ↗
Figure 10
Figure 10. Figure 10: Situation when α, β, γ, δ are of length at least five, and d = w. Definition 2.4. Given a cubic polyhedron G, we may associate to it a planar, bipartite, spanning subgraph G′ , that we will call the evenisation of G, in the following way. We begin by considering a partition of O into pairs {ω1, ω2}, {ω3, ω4}, . . . , {ω|O|−1, ω|O|} (2.6) such that the total distance between the corresponding vertices in t… view at source ↗
Figure 11
Figure 11. Figure 11: u1, uh, v1, vh must be ordered in this way around ρ. in this order, and in the other component of con(G′ ) there is a region containing x ′ 1 , x′ k , x′ h , z′ 1 , z′ 2 , z′ k , z′ h , x′ 2 in this order, where for i = 1, 2, h, k, either u ′ i = ui , v ′ i = vi , x ′ i = xi and z ′ i = zi , or u ′ i = xi , v ′ i = zi , x ′ i = ui , and z ′ i = vi . Therefore, the edges u1z1, uhzh, ukzk cannot all be adde… view at source ↗
Figure 12
Figure 12. Figure 12: If |O| = 4 then odd(G∗ ) ≃ K4. 3 Polyhedra of maximal degree 4: proof of Theorems 1.3 and 1.1 3.1 Preparatory results We begin by formally stating and proving a result mentioned in the introduction. Lemma 3.1. Let G be a graph such that ∆(G) ≥ 5. Then con(G) is non-planar. Proof. Let x be a vertex of degree d ≥ 5. The neighbours of x are pairwise adjacent in con(G), hence con(G) contains a subgraph isomor… view at source ↗
Figure 13
Figure 13. Figure 13: Situation for Lemma 3.3. We claim that i = 1. If we can prove it, then every d1b1-path in G must contain one of a1, x, c1, completing the proof of the present lemma. Suppose by contradiction that i ≥ 2. W.l.o.g., we may take z := dD = ai . We define a subgraph G′ of G consisting of the internally disjoint paths Pb of length B, Pc of length C 20 [PITH_FULL_IMAGE:figures/full_fig_p020_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: The eighteen possibilities for the minor [PITH_FULL_IMAGE:figures/full_fig_p021_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: Situation in Lemma 3.4. Proof. Due to Lemma 3.1, we may assume that ∆(G) = 4. Let x ∈ V (G) be a vertex of degree 4. By Lemma 3.3, {a, x, c} is a 3-cut of G, with a, c neighbours of x that are non-consecutive in the cyclic order. It follows that a, c belong to the external face of G. We claim that degG(a) = 3. By contradiction, we write NG(a) = {w, x, y, z} in this cyclic order, with y, a, z consecutive o… view at source ↗
Figure 16
Figure 16. Figure 16: deg(a) = 4 is impossible. Therefore, every vertex of degree 4 in G determines a 3-cut consisting of the vertex itself and two of its neighbours, that are not consecutive in the cyclic order, and that are of degree 3 in G. Every such 3-cut splits G into 2 components. We may then list the vertices of degree 4 of G as x1, x2, . . . , xn, n ≥ 1 such that for every 1 ≤ i ≤ n there is a 3-cut {ai , xi , ci} of … view at source ↗
Figure 17
Figure 17. Figure 17: Definition 3.5. Proposition 3.6. Let G be a polyhedron such that ∆(G) ≥ 4 and con(G) is planar. Then there is at least one odd face of G lying in each of G0 (3.1) and Gn (3.2). Proof. By contradiction, assume that all the internal regions of G0 correspond to even faces of G. By the handshaking lemma, the external region of G0 is thus also of even length, so that G0 is bipartite. Call x := x1, a := a1, c :… view at source ↗
Figure 18
Figure 18. Figure 18: Proposition 3.6, G0. By contradiction, assume that G# is not 3-connected. Since it is plane and 2-connected, there exist regions α, β of G# that have two common non-adjacent vertices. By construction, the same is true for G, contradiction. Clearly the reasoning for Gn is the same as for G0. 3.2 Concluding the proofs of Theorems 1.3 and 1.1 The following is an immediate consequence of Proposition 3.6. Coro… view at source ↗
Figure 19
Figure 19. Figure 19: Proposition 3.10, with j = m = 4, and m′ = 1. The thick lines delimit the cycles C0 of length 5 and Cn of length 13. Suppose by contradiction that con(G) is planar. Then by Proposition 3.6, the graph G0 contains at least one internal region ω0 corresponding to an odd face of G, and Gn contains at least one internal region ωn corresponding to an odd face of G. By assumption, O ̸= {ξda, ξab} and O ̸= {ξcd, … view at source ↗
Figure 20
Figure 20. Figure 20: Illustration of Proposition 3.11, with n = 11, i = 3, j = 7, and m = 12. Here we have C ′′′ : u, a2, a3, a4, a5, a6, a7, c12, v, c10, c9, a3, a4, a5, a6, a7, a8, a9, a10, a11, yielding the cycle u, a3, a5, a7, v, c9, a4, a6, a8, a10 in con(G). Lastly, if m is even and the distance between u, v on C ′′ is odd, we write u = a1 = cn−j+2 and v = cn−j+2h+1, with n − j + 1 + i < n − j + 2h + 1 ≤ m. We consider … view at source ↗
Figure 21
Figure 21. Figure 21: Proposition 1.9. a polyhedron, ui−2ui+2 ∈ E(G), impossible as n ̸= 5. We deduce that indeed αi , βi , γi , δi ̸= φ for every 1 ≤ i ≤ n. For 1 ≤ i ≤ n, by planarity of G we have βi+1, δi+1 ∈ {αi , βi , γi , δi}. Moreover, βi+1, δi+1 ̸∈ {αi , γi} e.g., if αi = βi+1, then this face contains ui , ui+3, impossible. It follows that βi+1, δi+1 ∈ {βi , δi}. Next, for 1 ≤ i ≤ n, we claim that βi ̸= δi . Indeed, if… view at source ↗
Figure 22
Figure 22. Figure 22: Lemma 5.5. The following result is at the heart of the proof of Theorem 1.11. Proposition 5.6. Let G be a polyhedron of maximal face length 4, such that facecon(G) is maximal planar. Then each connected component of the subgraph of G generated by the vertices lying on at least one quadrangular face is isomorphic to one of the two graphs in [PITH_FULL_IMAGE:figures/full_fig_p035_22.png] view at source ↗
Figure 23
Figure 23. Figure 23: Proposition 5.6. where for 1 ≤ i ≤ A, the face αi is adjacent to αi+1 and αi−1, with the indices taken modulo A. The edges of the faces (5.12) that are external to all of (5.12) form a cycle Cw : w1, w2, . . . , wW W ≥ 3 (5.13) with indices taken modulo W. If there are any edges of (5.12) that are internal to all of (5.12), then they form a cycle that we will call Cu : u1, u2, . . . , uU , 3 ≤ U ≤ W (5.14… view at source ↗
Figure 24
Figure 24. Figure 24: Illustration of the subgraphs Gu and Gw of G. Here A = 18, W = 22, and U = 14. Note that U + W = 2A. Then on one hand u1u3 ∈ E′ . As E′ ∩ E(facecon(Gu)) = ∅, this edge is external to Cu, thus by planarity of facecon(G), the vertex u2 is not adjacent to any vertex of Cw. On the other hand u2w1 ∈ E′ ⊂ E(facecon(G)), contradiction. Hence none of (5.12) contain three vertices of Cu. As we are assuming that we… view at source ↗
Figure 25
Figure 25. Figure 25: α2 = [u2, u3, w3, w2]. It remains to inspect what happens for connected components of H such that there is no cycle Cu i.e., there is a common vertex x to all the faces (5.12). We may write w.l.o.g. αi = [x, w2i−1, w2i , w2i+1], 1 ≤ i ≤ A = W/2 for even W ≥ 6, as in Figure 26a. Accordingly, facecon(G) has a subgraph as depicted in Figure 26b. In particular, x, w2i , w2i+1, w2i+2 is a 4-cycle in facecon(G)… view at source ↗
Figure 26
Figure 26. Figure 26: Case when α1, α2, . . . , αA have a common vertex x, with A = 5. Since facecon(G) is maximal planar, we deduce that w2iw2i+2 ∈ E(facecon(G)) for every 1 ≤ i ≤ A. Now each edge of facecon(G) corresponds in G either to an edge of a triangular face, or a diagonal of a quadrangular face. We claim that w2iw2i+2 ∈ E(G) for every 1 ≤ i ≤ A. By contradiction, suppose that w2w4 ̸∈ E(G) (we have chosen to fix i = 1… view at source ↗
Figure 27
Figure 27. Figure 27: w2w4 ̸∈ E(G). Then by planarity of facecon(G), there is no face of facecon(G) containing three of w1, w2, . . . , wW with even indices. It follows that in G, outside the cycle w2, w4, . . . , wW , we cannot insert any vertices or edges without contradicting the planarity of facecon(G) or the 3-connectivity of G. Hence [w2, w4, . . . , wW ] is a face in G. By assumption, the maximal face length of G is 4, … view at source ↗
Figure 28
Figure 28. Figure 28: If α1, α2, . . . , αA have a common vertex x, then w2iw2i+2 ∈ E(G) for every 1 ≤ i ≤ A. is quadrangular, then it is adjacent only to triangular faces, contradicting Lemma 5.5. Therefore W = 6, yielding the scenario in Figure 23b. An illustration of Proposition 5.6 is given by the leftmost graph in [PITH_FULL_IMAGE:figures/full_fig_p039_28.png] view at source ↗
Figure 29
Figure 29. Figure 29: Applying T2 to G replaces a triangular face of facecon(G) with the depicted triangulation. We close with a result of independent interest on the connectivity of facecongraphs. Proposition 5.7. Let G be a polyhedron satisfying odd(G∗ ) ≃ K2. Then facecon(G) is not 3- connected. Proof. Call φ1, φ2 the only two odd faces of G, and yz the edge belonging to both. We define G ′ = G − yz. (5.15) Hence G′ is a pl… view at source ↗
Figure 30
Figure 30. Figure 30: Proposition 5.7. Closing remarks and future work. Here we have completely classified the polyhedra G such that con(G) is planar (Theorem 1.1). Several intriguing questions arise naturally. The first con￾cerns the classification of all graphs G such that con(G) is planar/polyhedral. The second concerns the classification of polyhedra and more generally, plane graphs G such that facecon(G) is pla￾nar/polyhe… view at source ↗
read the original abstract

Given a polyhedron (planar, $3$-connected graph) $G$, we investigate its common neighbourhood graph con($G$). For cubic ($3$-regular) polyhedra, we show that the planarity of con($G$) depends on the number of odd faces of $G$, and on their adjacency. We then prove that for all other polyhedra, con($G$) is non-planar. We introduce a novel concept for polyhedra (and more generally, for plane graphs) $G$, namely the `facial common neighbourhood graph' facecon($G$). Its definition takes into account pairs of vertices with a common neighbour on the same face of $G$. It is a spanning subgraph of con($G$), that coincides with con($G$) for cubic polyhedra. It also generalises the reverse construction of the radial graph. As part of our investigation, we also prove a technical result of independent interest: if a maximal planar graph (triangulation of the sphere) has exactly two vertices of odd degree, then they are not adjacent. We also answer several questions in extremal graph theory. Fixing the number of vertices, we characterise the polyhedra $G$ such that con($G$) is planar and the number of edges in con($G$) is minimal/maximal. We address the same problem for facecon($G$), and prove that if it is maximal planar, then $G$ has no face of length greater than $6$. We notably characterise and explicitly construct all polyhedra $G$ of maximal face length $4$ such that facecon($G$) is maximal planar.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper defines the common neighbourhood graph con(G) for polyhedra G (3-connected planar graphs). For cubic polyhedra, planarity of con(G) depends on the number of odd faces and their adjacency; for all non-cubic polyhedra, con(G) is non-planar. It introduces the facial common neighbourhood graph facecon(G), a spanning subgraph of con(G) that coincides with it for cubic cases and generalizes the reverse radial graph. A technical lemma of independent interest states that a maximal planar graph with exactly two odd-degree vertices has those vertices non-adjacent. The paper characterizes, for fixed number of vertices, the polyhedra extremizing the edge count in con(G) and facecon(G), proves that maximal-planar facecon(G) implies no face longer than 6, and explicitly constructs all maximum-face-length-4 polyhedra with facecon(G) maximal planar.

Significance. If the claims hold, the work contributes to the study of derived graphs on polyhedra by giving planarity criteria tied to facial parity and adjacency, plus complete extremal characterizations with explicit constructions. The technical lemma on odd-degree vertices in triangulations has potential independent value in graph theory. The generalization via facecon(G) and the link to radial graphs strengthen the contribution to embedded-graph combinatorics.

minor comments (3)
  1. §2 (Definitions): An early small example contrasting con(G) and facecon(G) for a non-cubic polyhedron would clarify the spanning-subgraph relation and the role of facial common neighbors.
  2. Theorem 5.3 (extremal characterization for facecon(G)): The statement that G has no face of length >6 when facecon(G) is maximal planar would benefit from an explicit reference to the Euler formula or handshaking lemma used in the proof.
  3. Figure 4 (construction for max-face-length 4): The caption should indicate the number of vertices and confirm that the depicted graph is 3-connected planar.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript, for the accurate summary of our results, and for recommending acceptance. We are pleased that the contributions to derived graphs on polyhedra, the planarity criteria, the technical lemma, and the extremal characterizations were viewed positively.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper defines con(G) and facecon(G) directly from the common-neighborhood relation on vertices of a 3-connected planar graph (polyhedron), then proves planarity criteria, extremal edge counts, and a technical lemma on odd-degree vertices in maximal planar graphs using standard tools such as Euler's formula, the handshaking lemma, and local embedding arguments. No step reduces a claimed prediction or uniqueness result to a fitted parameter, a self-citation chain, or a redefinition of the input; the derivations remain independent of the opening assumptions once the graphs are fixed.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The central claims rest on standard definitions of polyhedra as 3-connected planar graphs and on basic facts from planar graph theory. No free parameters are fitted. The new graph facecon(G) is a definitional construction rather than a postulated physical entity.

axioms (2)
  • domain assumption A polyhedron is a 3-connected planar graph (or equivalently a plane graph).
    Invoked in the first sentence of the abstract and used to define con(G) and facecon(G).
  • standard math Standard facts about planar graphs and degrees (handshaking lemma, Euler's formula) hold.
    Implicit background used in proofs involving odd faces and odd-degree vertices.
invented entities (1)
  • facial common neighbourhood graph facecon(G) no independent evidence
    purpose: To refine con(G) by considering only common neighbors on the same face and to generalize the reverse radial graph.
    New definition introduced in the abstract; it is a spanning subgraph of con(G) that coincides with it for cubic polyhedra.

pith-pipeline@v0.9.0 · 5816 in / 1760 out tokens · 55808 ms · 2026-05-20T16:34:25.088980+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

  1. [1]

    Alwardi, B

    A. Alwardi, B. Arsic, I. Gutman, and N. D. Soner. The common neighborhood graph and its energy.Iranian Journal of Mathematical Sciences and Informatics, 7(2):1–8, 2012

    work page 2012

  2. [2]

    Generation of simple quadrangulations of the sphere.Discrete Mathematics, 305(1-3):33–54, Dec

    G.Brinkmann, S.Greenberg, C.Greenhill, B.D.McKay, R.Thomas, andP.Wollan. Generation of simple quadrangulations of the sphere.Discrete Mathematics, 305(1-3):33–54, Dec. 2005

    work page 2005

  3. [3]

    R. Diestel. Graph theory 3rd ed.Graduate texts in mathematics, 173, 2005

    work page 2005

  4. [4]

    Gaspoz and R

    S. Gaspoz and R. W. Maffucci. Independence numbers of polyhedral graphs.Applied Mathe- matics and Computation, 462:128349, 2024

    work page 2024

  5. [5]

    Hollowbread-Smith and R

    P. Hollowbread-Smith and R. W. Maffucci. Generation of 3-connected, planar line graphs. Discrete Mathematics, 348(2):114302, 2025

    work page 2025

  6. [6]

    M. Knor, B. Luzar, R. Skrekovski, and I. Gutman. On Wiener index of common neighborhood graphs.MATCH Commun. Math. Comput. Chem, 72(1):321–332, 2014

    work page 2014

  7. [7]

    R. W. Maffucci. Classification and construction of planar, 3-connected Kronecker products. arXiv:2402.01407

    work page arXiv

  8. [8]

    R. W. Maffucci. Classification of polyhedral graphs by numbers of common neighbours. arXiv:2508.01349

    work page arXiv

  9. [9]

    R. W. Maffucci. Common neighbours in planar graphs.arXiv:2511.19251

    work page arXiv

  10. [10]

    R. W. Maffucci. Deza graphs and regular polyhedra.The Art of Discrete and Applied Mathe- matics

    work page

  11. [11]

    R. W. Maffucci. Regularity and separation for Sierpiński products of graphs.arXiv:2506.16864

    work page arXiv

  12. [12]

    R. W. Maffucci and N. Willems. On smallest 3-polytopes of given graph radius.Discrete Mathematics, 346(5):113322, 2023

    work page 2023

  13. [13]

    Schweitzer

    P. Schweitzer. Iterated open neighborhood graphs and generalizations.Discrete Applied Math- ematics, 161(10-11):1598–1609, 2013

    work page 2013

  14. [14]

    Sonntag and H.-M

    M. Sonntag and H.-M. Teichert. Iterated neighborhood graphs.Discussiones Mathematicae Graph Theory, 32(3):403–417, 2012

    work page 2012

  15. [15]

    Steinitz and H

    E. Steinitz and H. Rademacher. Vorlesungen über die Theorie der Polyeder. Springer 1934

    work page 1934

  16. [16]

    Tian and R

    H. Tian and R. Zafarani. Exploiting common neighbor graph for link prediction. InProceedings of the 29th ACM International Conference on Information & Knowledge Management, pages 3333–3336, 2020

    work page 2020

  17. [17]

    W. T. Tutte. A theory of 3-connected graphs.Indag. Math, 23(441-455):8, 1961

    work page 1961

  18. [18]

    H. Whitney. Congruent graphs and the connectivity of graphs.American Journal of Mathe- matics, 54(1):150–168, 1932. 42

    work page 1932