Molecular Directed, Bidirected, and Multidirected Graphs

1.1 Bidirected and Multidirected Graphs

Graph theory studies vertices and edges, modeling pairwise relationships, enabling analysis of networks, con-nectivity, paths, cycles, and structures [1]. A directed graph (or digraph) consists of a finite vertex set V and a set of ordered edges E ⊆ V × V , each edge (u, v) indicating a one-way connection from u (source) to v (target) [2, 3]. A bidirected graph is a generalization of an undirected graph where each edge is assigned a direction at each of its endpoints independently, allowing more expressive edge orientation [4, 5].

Definition 1 (Directed Graph). [1] A directed graph (or digraph) is a pair G = (V,E),

• V is a finite set of vertices, and • E ⊆ V × V is a set of ordered pairs called directed edges (or arcs).

Each edge (u, v) ∈ E represents a connection directed from vertex u (the tail) to vertex v (the head).

Example 1 (Directed Graph example: Hydrogen chloride polarity (H→Cl)). (cf.[6]) Consider the molecule HCl. Take the vertex set V = {H,Cl} and define the directed edge set E = {(H,Cl)} ⊆ V × V.

Thus G = (V,E) is a directed graph (digraph) whose single arc (H,Cl) encodes the orientation of the polar covalent bond from hydrogen (tail) to chlorine (head).

Definition 2 (Bidirected Graph). [4] A bidirected graph B = (G, τ) is given by G = (V,E), τ : V × E → {−1, 0, 1}, where:

• G is a simple undirected graph on vertex set V and edge set E.

• For each vertex-edge pair (v,e),  +1, if e is directed toward v, τ(v, e) = −1, if e is directed away from v, 0, if v is not incident to e.

We call G the underlying graph and τ the bidirection function.

Example 2 (Bidirected Graph example: Ammonia–borane dative bond NH3 → BH3). (cf.[7]) Let the underlying simple undirected graph be G = (V,E) with V = {N,B}, E = {N,B} = {e}.

Define the bidirection function τ : V × E → {−1, 0, 1} by τ(N,e) = −1 and τ(B,e) = +1, with τ(v,e) = 0 for any nonincident pair (none here). Then B = (G, τ) is a bidirected graph in which the edge is locally oriented “away from” N and “toward” B, encoding the donor (N) → acceptor (B) dative interaction.

A multidirected graph is a structure with vertices and edges, where edges may repeat, sources and targets are assigned, and multiplicities recorded[8, 9, 10].

Definition 3 (Multidirected Graph). [8, 9, 10] A multidirected graph is a tuple G = (V,E,s, t, m), • V is a finite set of vertices, • E is a finite set of edges, • s, t : E → V assign to each edge its source and target, • m : V × V → N0 gives the multiplicity of edges from one vertex to another.

Example 3 (Multidirected Graph example: Carbon monoxide triple bond as multiplicity). (cf.[11]) Model CO with a multidirected graph G = (V,E,s, t, m) where V = {C, O}, E = {e1, e2, e3}, s(ei) = C, t(ei) = O (i = 1, 2, 3).

Define the multiplicity map m : V × V → N0 by m(C, O) = {e ∈ E : s(e) = C, t(e) = O} = 3, m(u, v) = 0 for all (u, v) ̸= (C, O).

Thus G encodes the C≡O triple bond as three parallel directed edges from C to O with consistent multiplicity.

1.2 Molecular Graph

A molecular graph models a molecule with atoms as vertices and bonds as edges, representing its structural connectivity [12, 13, 14, 15, 16, 17]. Related concepts include molecular hypergraphs [18, 19, 20, 21], which extend this framework to capture higher-order interactions among multiple atoms simultaneously.

Definition 4 (Molecular Graph). [12, 13] A molecular graph is a finite, simple, undirected graph G = (V,E) in which each vertex v ∈ V represents an atom and each edge e = {u, v} ∈ E represents a chemical bond between atoms u and v. (Optionally, vertex/edge labels may encode atom types and bond types or orders.)

Example 4 (Molecular Graph example: Methane (CH4) connectivity). (cf.[22]) A molecular graph is a finite simple undirected graph whose vertices are atoms and edges are chemical bonds. For methane, let V = {C, H1, H2, H3, H4}, E = {C, H1}, {C, H2}, {C, H3}, {C, H4} .

Then G = (V,E) captures the tetrahedral connectivity of CH4 without imposing any edge orientation.

2.1 Molecular Directed Graph

A molecular directed graph represents atoms as labeled vertices and chemical bonds as directed edges, capturing oriented molecular interactions.

Definition 5 (Molecular Directed Graph (MDG)). Fix finite attribute sets ΣV (vertex/atom attributes, e.g., element, charge, isotope) and ΣE (edge/bond attributes, e.g., bond order, stereo). A molecular directed graph is a tuple MD = (V,E,s, t, λV , λE),

• V is a finite set of vertices (atoms), • E is a finite set of edges (bonds), • s, t : E → V assign to each edge e ∈ E its source s(e) and target t(e), • λV : V → ΣV labels each vertex with its atomic attributes, • λE : E → ΣE labels each edge with its bond attributes.

We write the underlying directed edge set of MD as E→ := { (s(e), t(e)) | e ∈ E } ⊆ V × V.

Example 5 (Ammonia (NH3): three polar N–H bonds oriented Hi → N). (cf.[23]) Let ΣV = {N, H} and ΣE = {single}. Define the MDG MD = (V,E,s, t, λV , λE) by V = {N,H1, H2, H3}, E = {e1, e2, e3}, s(ei) = Hi, t(ei) = N (i = 1, 2, 3).

Label vertices and edges as λV (N) = N, λV (Hi) = H (i = 1, 2, 3), λE(ei) = single (i = 1, 2, 3).

The underlying directed edge set is E→ = {(H1, N), (H2, N), (H3, N)}, encoding the polarity of each N–H bond from hydrogen (source) to nitrogen (target).

Example 6 (Carbon dioxide (CO2): two polar C=O bonds oriented C → Oi). Let ΣV = {C, O} and ΣE = {double}. Define MD = (V,E,s, t, λV , λE)

V = {C, O1, O2}, E = {e1, e2}, s(e1) = C, t(e1) = O1, s(e2) = C, t(e2) = O2.

Vertex and edge labels are λV (C) = C, λV (Oi) = O (i = 1, 2), λE(e1) = λE(e2) = double.

Thus E→ = {(C, O1), (C, O2)}, representing both C=O bonds by directed edges from carbon to oxygen (one per oxygen). Multiplicity information (double bonds) is carried here only as an edge label.

Example 7 (Sodium chloride (NaCl): ionic interaction oriented Na → Cl). (cf.[24]) Let ΣV = {Na, Cl} and ΣE = {ionic}. Define MD = (V,E,s, t, λV , λE) by V = {N a, Cl}, E = {e}, s(e) = N a, t(e) = Cl.

Set the labels λV (Na) = Na, λV (Cl) = Cl, λE(e) = ionic.

Then E→ = {(N a, Cl)}, capturing the ionic character by a single directed edge pointing from sodium (donor/source) to chlorine (acceptor/target).

Example 8 (Water (polar O–H bonds as oriented edges)). (cf.[25]) Let ΣV = {H, O} and ΣE = {single}. Define the MDG MD = (V,E,s, t, λV , λE) by V = {O,H1, H2}, E = {e1, e2}, s(e1) = H1, t(e1) = O, s(e2) = H2, t(e2) = O, λV (O) = O, λV (Hi) = H (i = 1, 2), λE(ej) = single (j = 1, 2).

Thus E→ = {(H1, O), (H2, O)} captures the polarity (hydrogen → oxygen).

Example 9 (Hydrogen chloride (H→Cl bond polarity)). (cf.[26]) Let ΣV = {H, Cl} and ΣE = {single}. Define MD = (V,E,s, t, λV , λE)

V = {H,Cl}, E = {e}, s(e) = H, t(e) = Cl, λV (H) = H, λV (Cl) = Cl, λE(e) = single.

Then E→ = {(H,Cl)} represents the oriented H–Cl bond.

Theorem 1 (MDG generalizes a directed graph). Let Dig denote the class of finite directed graphs G = (V,E→) with E→ ⊆ V × V . There exist maps UD : MD 7→ (V,E→) ∈ Dig, ID : (V,E→) 7→ MD such that UD ◦ ID = idDig. Hence every directed graph is (canonically) a special case of a molecular directed graph.

Proof : Define the forgetful map UD(V, E, s, t, λV , λE) := (V, {(s(e), t(e)) : e ∈ E}) ∈ Dig.

Given any G = (V, E→) ∈ Dig, define the trivial-label embedding ID(G) := (V, E, s, t, λV , λE), by taking E := E→, s(u, v) := u, t(u, v) := v for each (u, v) ∈ E→, and choosing fixed elements v∗ ∈ ΣV , e∗ ∈ ΣE with λV (v) := v∗ for all v ∈ V, λE(e) := e∗ for all e ∈ E.

Then UD ID(G) = (V, {(s(u, v), t(u, v)) : (u, v) ∈ E→}) = (V, E→) = G, so UD ◦ ID = idDig. Therefore every directed graph is realized as an MDG with constant labels, and every MDG forgets to a directed graph via UD. □

2.2 Molecular BiDirected Graph

A molecular bidirected graph models atoms as labeled vertices with edges independently directed at endpoints, encoding bidirectional or asymmetric bond orientations.

Definition 6 (Molecular BiDirected Graph (MBDG)). Fix finite attribute sets ΣV and ΣE. A molecular bidirected graph is a quintuple MB = (V,E,τ,λV , λE),

• V is a finite set of vertices and E a finite set of (undirected) edges, • τ : V × E → {−1, 0, 1} is a bidirection function satisfying:

τ(v,e) = 0 if v is not incident to e; τ(v, e) = +1 if e is directed toward v at v; τ(v, e) = −1 if e is directed away from v at v; • λV : V → ΣV and λE : E → ΣE assign molecular attributes to vertices/edges.

The underlying bidirected graph is (G, τ) with G = (V, E).

Example 10 (Ammonia–borane dative bond: NH3 → BH3 ). (cf.[7]) Let ΣV = {N, B}, ΣE = {dative}. Consider the MBDG MB = (V,E,τ,λV , λE), V = {N,B}, E = {e}, with bidirection function τ : V × E → {−1, 0, 1} given by τ(N,e) = −1, τ(B,e) = +1, and vertex/edge labels λV (N) = N, λV (B) = B, λE(e) = dative.

Nonincident pairs map to 0 by definition. Endpoint signs encode “away from N” and “toward B”.

Example 11 (Diammine copper(II): two N→Cu donations). (cf.[27]) Let ΣV = {Cu, N}, ΣE = {dative} and define MB = (V,E,τ,λV , λE), V = {Cu,N1, N2}, E = {e1, e2},

τ(N1, e1) = −1, τ(Cu,e1) = +1, τ(N2, e2) = −1, τ(Cu,e2) = +1, (all other τ(·, ·) = 0), and labels λV (Cu) = Cu, λV (Ni) = N, λE(ei) = dative (i = 1, 2).

Each edge is oriented locally from N (donor) to Cu (acceptor) via τ.

Example 12 (Acetone–boron trifluoride adduct: O→B donation). (cf.[28]) Let ΣV = {O, B} and ΣE = {dative}. Define the MBDG MB = (V,E,τ,λV , λE), V = {Oac, B}, E = {e}.

The bidirection function τ : V × E → {−1, 0, 1} is τ(Oac, e) = −1, τ(B,e) = +1, and τ(v,e′) = 0 for any nonincident pair (none here). Vertex/edge labels are λV (Oac) = O, λV (B) = B, λE(e) = dative.

At the oxygen endpoint the edge is locally “away” (−1), and at boron it is “toward” (+1), encoding the coordinate bond donation from the carbonyl oxygen of acetone to BF3.

Example 13 (Iron–carbonyl unit: σ donation and π backbonding (two bidirected edges)). (cf.[29]) Let ΣV = {Fe, CO} and ΣE = {σ-donation, π-backbonding}. Consider MB = (V,E,τ,λV , λE), V = {Fe, CO}, E = {eσ, eπ}.

Define τ on incident pairs by τ(CO,eσ) = −1, τ(Fe, eσ) = +1 (CO → Fe σ-donation), τ(Fe, eπ) = −1, τ(CO,eπ) = +1 (Fe → CO π-backbonding), and set τ(·, ·) = 0 for all nonincident pairs. Labels are λV (Fe) = Fe, λV (CO) = CO, λE(eσ) = σ-donation, λE(eπ) = π-backbonding.

Thus the σ edge is locally oriented away from CO and toward Fe, while the π edge is locally oriented away from Fe and toward CO, capturing the classical synergic bonding picture of metal–carbonyl complexes within the bidirected framework.

Theorem 2 (MBDG generalizes a bidirected graph). Let BiDig denote the class of finite bidirected graphs B = (G, τ) with G = (V,E). There exist maps UB : MB 7→ (G, τ) ∈ BiDig, IB : (G, τ) 7→ MB such that UB ◦ IB = idBiDig.

Proof : Define the forgetful map UB(V, E, τ, λV , λE) := ((V, E), τ). Given B = ((V, E), τ) ∈ BiDig, fix v∗ ∈ ΣV , e∗ ∈ ΣE and define IB(B) := (V, E, τ, λV , λE), λV (v) := v∗ ∀v ∈ V, λE(e) := e∗ ∀e ∈ E.

Then UB(IB(B)) = ((V, E), τ) = B, hence UB ◦IB = idBiDig. Thus every bidirected graph appears as an MBDG with constant labels, and every MBDG forgets to a bidirected graph. □

2.3 Molecular MultiDirected Graph

A molecular multidirected graph extends directed models by allowing multiple labeled directed edges between atoms, capturing multiplicities and parallel chemical interactions.

Definition 7 (Molecular MultiDirected Graph (MMDG)). Fix finite attribute sets ΣV and ΣE. A molecular multidirected graph is a septuple MM = (V,E,s, t, m, λV , λE),

• V is a finite set of vertices, E a finite set of edges, • s, t : E → V assign the source and target of each edge, • m : V × V → N0 records multiplicities and is required to satisfy the consistency constraint m(u, v) = { e ∈ E : s(e) = u, t(e) = v } for all (u, v) ∈ V × V,

• λV : V → ΣV and λE : E → ΣE assign molecular attributes.

The underlying multidirected graph is (V,E,s, t, m).

Example 14 (Dimethyl sulfoxide S=O double bond as parallel directed edges). Let ΣV = {S, O}, ΣE = {σ, π} and define MM = (V,E,s, t, m, λV , λE) by V = {S, O}, E = {eσ, eπ}, s(eσ) = s(eπ) = S, t(eσ) = t(eπ) = O, λV (S) = S, λV (O) = O, λE(eσ) = σ, λE(eπ) = π.

Then the multiplicity function satisfies m(S, O) = {e ∈ E : s(e) = S, t(e) = O} = 2, m(u, v) = 0 otherwise.

Thus the S=O double bond is modeled by two parallel directed edges S → O.

Example 15 (Carbon monoxide C≡O triple bond as three parallel directed edges). Let ΣV = {C, O}, ΣE = {σ, π1, π2} and define MM = (V,E,s, t, m, λV , λE)

V = {C, O}, E = {eσ, eπ1 , eπ2 }, s(e) = C, t(e) = O for all e ∈ E, λV (C) = C, λV (O) = O, λE(eσ) = σ, λE(eπ1 ) = π1, λE(eπ2 ) = π2.

Hence m(C, O) = 3, m(u, v) = 0 otherwise, capturing a triple bond as three parallel directed edges in the same orientation C → O.

Example 16 (Carbon dioxide: two C=O double bonds as four parallel directed edges). (cf.[30, 31]) Let ΣV = {C, O} and ΣE = {σ, π}. Define the MMDG MM = (V,E,s, t, m, λV , λE) by V = {C, O1, O2}, E = {eσ,1, eπ,1, eσ,2, eπ,2}.

Assign sources and targets s(eσ,i) = C, t(eσ,i) = Oi, s(eπ,i) = C, t(eπ,i) = Oi (i = 1, 2), so each C–O bond is represented by two parallel directed edges C → Oi. Label vertices and edges by λV (C) = C, λV (Oi) = O (i = 1, 2), λE(eσ,i) = σ, λE(eπ,i) = π.

The multiplicity function m : V × V → N0 satisfies m(C, O1) = {e ∈ E : s(e) = C, t(e) = O1} = 2, m(C, O2) = 2, m(u, v) = 0 otherwise.

Thus the linear O=C=O structure is captured as two C=O double bonds, each modeled by a σ and a π edge in the same orientation C → Oi.

Example 17 (Metal–carbonyl synergy: CO→Ni σ donation and Ni→CO π backbonding). (cf.[32]) Let ΣV = {Ni, CO} and ΣE = {σ-donation, π-backbonding}. Consider MM = (V,E,s, t, m, λV , λE), V = {N i, CO}, E = {eσ, eπ}.

Assign directions to encode the synergic interaction:

s(eσ) = CO, t(eσ) = Ni (σ donation CO → Ni), s(eπ) = N i, t(eπ) = CO (π backbonding Ni → CO). Set labels λV (Ni) = Ni, λV (CO) = CO, λE(eσ) = σ-donation, λE(eπ) = π-backbonding.

The multiplicity map is then m(CO,Ni) = {e ∈ E : s(e) = CO, t(e) = Ni} = 1, m(N i, CO) = {e ∈ E : s(e) = N i, t(e) = CO} = 1, m(u, v) = 0 for all other ordered pairs (u, v).

Hence this MMDG simultaneously represents two directed interactions between the same pair of vertices with opposite orientations and distinct edge labels, reflecting the classical σ/π synergy in metal–carbonyl bonding.

Theorem 3 (MMDG generalizes a multidirected graph). Let MultiDig denote the class of finite multidirected graphs G = (V,E,s, t, m) satisfying m(u, v) = |{e ∈ E : s(e) = u, t(e) = v}|. There exist maps UM : MM 7→ (V,E,s, t, m) ∈ MultiDig, IM : (V,E,s, t, m) 7→ MM such that UM ◦ IM = idMultiDig.

Proof : Define the forgetful map UM (V, E, s, t, m, λV , λE) := (V, E, s, t, m).

Given (V, E, s, t, m) ∈ MultiDig, choose fixed v∗ ∈ ΣV , e∗ ∈ ΣE and put IM (V, E, s, t, m) := (V, E, s, t, m, λV , λE), λV (v) := v∗ ∀v ∈ V, λE(e) := e∗ ∀e ∈ E.

Then UM (IM (V, E, s, t, m)) = (V, E, s, t, m), so UM ◦ IM = idMultiDig. Hence every multidirected graph is a special case of an MMDG with constant labels, and every MMDG forgets to a multidirected graph. □

Lemma 1 (Conservative extension). In each of the three settings (MDG, MBDG, MMDG), taking ΣV and ΣE to be singletons yields exactly the corresponding classical structure (directed, bidirected, multidirected) on the same carrier sets.

Proof : Let ΣV = {∗} and ΣE = {⋄}. Then all label maps λV , λE are uniquely determined and carry no additional information. The defining tuples reduce, under UD, UB, UM , to the classical data (V, E→), ((V, E), τ), and (V, E, s, t, m) respectively, with no loss or addition beyond the classical structures. Thus the molecular variants are conservative extensions. □

Lemma 2 (Exact retrieval via forgetful maps). For each molecular structure M ∈ {MD, MB, MM }, the corresponding forgetful map U ∈ {UD, UB, UM } returns the exact classical object obtained by discarding labels and keeping only the incidence/orientation data.

Proof : Immediate from the definitions of UD, UB, UM , which simply erase λV , λE and retain the structural maps (either (s, t), or τ, together with E and V ). The equalities UD(MD) = (V, E→), UB(MB) = ((V, E), τ), UM (MM ) = (V, E, s, t, m) hold by construction. □