Hubbry Logo
Graph propertyGraph propertyMain
Open search
Graph property
Community hub
Graph property
logo
8 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Graph property
Graph property
Graph property
View on Wikipedia
from Wikipedia
An example graph, with the properties of being planar and being connected, and with order 6, size 7, diameter 3, girth 3, vertex connectivity 1, and degree sequence <3, 3, 3, 2, 2, 1>

In graph theory, a graph property or graph invariant is a property of graphs that depends only on the abstract structure, not on graph representations such as particular labellings or drawings of the graph.[1]

Definitions

[edit]

While graph drawing and graph representation are valid topics in graph theory, in order to focus only on the abstract structure of graphs, a graph property is defined to be a property preserved under all possible isomorphisms of a graph. In other words, it is a property of the graph itself, not of a specific drawing or representation of the graph. Informally, the term "graph invariant" is used for properties expressed quantitatively, while "property" usually refers to descriptive characterizations of graphs. For example, the statement "graph does not have vertices of degree 1" is a "property" while "the number of vertices of degree 1 in a graph" is an "invariant".

More formally, a graph property is a class of graphs with the property that any two isomorphic graphs either both belong to the class, or both do not belong to it.[1] Equivalently, a graph property may be formalized using the indicator function of the class, a function from graphs to Boolean values that is true for graphs in the class and false otherwise; again, any two isomorphic graphs must have the same function value as each other. A graph invariant or graph parameter may similarly be formalized as a function from graphs to a broader class of values, such as integers, real numbers, sequences of numbers, or polynomials, that again has the same value for any two isomorphic graphs.[2]

Properties of properties

[edit]

Many graph properties are well-behaved with respect to certain natural partial orders or preorders defined on graphs:

  • A graph property P is hereditary if every induced subgraph of a graph with property P also has property P. For instance, being a perfect graph or being a chordal graph are hereditary properties.[1]
  • A graph property is monotone if every subgraph of a graph with property P also has property P. For instance, being a bipartite graph or being a triangle-free graph is monotone. Every monotone property is hereditary, but not necessarily vice versa; for instance, subgraphs of chordal graphs are not necessarily chordal, so being a chordal graph is not monotone.[1]
  • A graph property is minor-closed if every graph minor of a graph with property P also has property P. For instance, being a planar graph is minor-closed. Every minor-closed property is monotone, but not necessarily vice versa; for instance, minors of triangle-free graphs are not necessarily themselves triangle-free.[1]

These definitions may be extended from properties to numerical invariants of graphs: a graph invariant is hereditary, monotone, or minor-closed if the function formalizing the invariant forms a monotonic function from the corresponding partial order on graphs to the real numbers.

Additionally, graph invariants have been studied with respect to their behavior with regard to disjoint unions of graphs:

  • A graph invariant is additive if, for all two graphs G and H, the value of the invariant on the disjoint union of G and H is the sum of the values on G and on H. For instance, the number of vertices is additive.[1]
  • A graph invariant is multiplicative if, for all two graphs G and H, the value of the invariant on the disjoint union of G and H is the product of the values on G and on H. For instance, the Hosoya index (number of matchings) is multiplicative.[1]
  • A graph invariant is maxing if, for all two graphs G and H, the value of the invariant on the disjoint union of G and H is the maximum of the values on G and on H. For instance, the chromatic number is maxing.[1]

In addition, graph properties can be classified according to the type of graph they describe: whether the graph is undirected or directed, whether the property applies to multigraphs, etc.[1]

Values of invariants

[edit]

The target set of a function that defines a graph invariant may be one of:

Graph invariants and graph isomorphism

[edit]

Easily computable graph invariants are instrumental for fast recognition of graph isomorphism, or rather non-isomorphism, since for any invariant at all, two graphs with different values cannot (by definition) be isomorphic. Two graphs with the same invariants may or may not be isomorphic, however.

A graph invariant I(G) is called complete if the identity of the invariants I(G) and I(H) implies the isomorphism of the graphs G and H. Finding an efficiently-computable such invariant (the problem of graph canonization) would imply an easy solution to the challenging graph isomorphism problem. However, even polynomial-valued invariants such as the chromatic polynomial are not usually complete. The claw graph and the path graph on 4 vertices both have the same chromatic polynomial, for example.

Examples

[edit]

Properties

[edit]

Integer invariants

[edit]

Real number invariants

[edit]

Sequences and polynomials

[edit]

Edge partition

[edit]

See also

[edit]
[edit]

References

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Graph property

View on Grokipedia
from Grokipedia
In , a is a structural characteristic of graphs that is preserved under , meaning it depends only on the abstract combinatorial structure and not on any specific vertex labeling or representation. Formally, it is defined as a family of graphs closed under , where two graphs satisfy the property one can be obtained from the other by relabeling vertices while preserving adjacency relations. Graph properties encompass a wide range of structural features and are central to understanding graph behavior. Notable examples include connectivity, which holds if there is a path between every pair of vertices; bipartiteness, where the vertices can be partitioned into two disjoint independent sets with all edges between them; and planarity, which allows the graph to be drawn in the plane without edge crossings. Other significant properties involve coloring, such as the chromatic number, the minimum number of colors needed to color vertices so that no adjacent vertices share the same color, and cycle-related traits like being Eulerian (admitting a cycle that traverses each edge exactly once) or Hamiltonian (admitting a cycle that visits each vertex exactly once). Properties are often categorized by their closure behaviors, which reveal how they interact with graph modifications. A monotone graph property is closed under the removal of edges and vertices, implying that if a graph satisfies it, all its subgraphs do as well; examples include triangle-freeness or having maximum degree at most kk. In contrast, a hereditary graph property is closed under taking s, meaning the property persists in any , and such properties can be characterized by forbidden s, like being C4C_4-free (containing no induced 4-cycle). These classifications aid in analyzing graph families and their extremal sizes. Graph properties find extensive applications in , which determines the maximum number of edges in graphs avoiding certain forbidden structures, and in algorithmic contexts like property testing, where efficient algorithms verify whether a graph satisfies a by querying a small portion of its structure. For instance, monotone properties are testable with constant query complexity in the model, highlighting their computational tractability.

Core Concepts

Definition

In , a graph GG is formally defined as an (V,E)(V, E), where VV is a of vertices (also called nodes) and EE is a set of unordered pairs of distinct vertices from VV, representing edges that connect them. This structure captures pairwise relationships between elements, such as connections in networks or dependencies in systems. A is a bijective mapping f:V(G)→V(H)f: V(G) \to V(H) between the vertex sets of two graphs GG and HH such that two vertices in GG are adjacent if and only if their images under ff are adjacent in HH. Isomorphic graphs are considered structurally identical, differing only in the labeling or naming of their vertices and edges. A graph property is a family of graphs that is closed under ; that is, for a PP of all possible graphs, if G∈PG \in P and HH is isomorphic to GG, then H∈PH \in P. Equivalently, it is any characteristic of graphs that depends solely on their abstract structure, independent of specific vertex or edge labels. Graph properties are typically defined on unlabeled graphs, which are equivalence classes of labeled graphs under isomorphism, ensuring that relabeling does not alter membership in PP. In contrast, labeled graphs assign distinct identifiers to vertices, but properties ignore such labels to focus on relational structure. Basic examples include being a simple graph (no loops or multiple edges between the same pair of vertices), which is essential in modeling real-world networks without self-references or duplicate connections; being undirected (edges have no direction), common in symmetric relations like social ties; and being finite, which aligns with computational tractability in design and . These properties provide foundational building blocks for more complex analyses in areas such as optimization and representation. Graph invariants, such as the number of vertices, represent a subclass where the property assigns a specific value preserved under rather than a binary yes/no .

Invariance under Graph Isomorphism

is defined as a bijective mapping between the vertex sets of two graphs that preserves the adjacency relation, meaning two vertices are adjacent in one graph if and only if their images under the mapping are adjacent in the other. This structure-preserving ensures that isomorphic graphs have identical connectivity patterns, disregarding any arbitrary labeling of vertices. Graph properties are required to be invariant under to capture the intrinsic structural features of a graph, independent of vertex labels or representations, thereby avoiding inconsistencies arising from superficial labeling differences. To see this formally, suppose GG and HH are isomorphic via a ϕ:V(G)→V(H)\phi: V(G) \to V(H) that preserves edges, and let PP be a defined solely in terms of adjacency relations. If P(G)P(G) holds, then for any edge or non-edge in GG, the corresponding structure in HH under ϕ\phi satisfies the same relational conditions, implying P(H)P(H) also holds; otherwise, PP would depend on labeling artifacts rather than the underlying structure, leading to contradictory classifications of equivalent graphs. This invariance principle ensures that reliably distinguish graphs based on their combinatorial essence. The foundational role of isomorphism invariance was recognized early in graph theory's development, notably in Hassler Whitney's 1932 work on congruent graphs, which explored mappings preserving graph connectivity, and in Dénes Kőnig's 1936 monograph Theory of Finite and Infinite Graphs, which systematized graph structures with explicit consideration of in . These contributions underscored invariance as essential to the field's theoretical framework. Such invariance has profound implications for graph recognition, as it permits the categorization of graphs up to , treating all relabelings of the same structure as equivalent and facilitating the study of graph classes without regard to representational details. This approach underpins algorithms and theorems that classify graphs by shared properties, enabling efficient identification of structural similarities across diverse applications.

Classification of Properties

Hereditary Properties

A hereditary graph property is a class of graphs that is closed under the operation of taking induced subgraphs. Formally, if a graph GG belongs to the property P\mathcal{P} and HH is an induced subgraph of GG, then HH also belongs to P\mathcal{P}. This closure ensures that the property is preserved when vertices and the edges between them are removed, making it "inherited" by substructures. Such properties are fundamental in because they capture structural constraints that remain invariant under vertex deletion. Hereditary properties are precisely those that can be characterized by a family of forbidden induced subgraphs, possibly infinite. That is, a graph belongs to P\mathcal{P} if and only if it contains none of the graphs in the forbidden family F(P)\mathcal{F}(\mathcal{P}) as an induced subgraph. The minimal elements of F(P)\mathcal{F}(\mathcal{P}) fully define the property, as any graph inducing a forbidden subgraph must contain a minimal one. This characterization distinguishes hereditary properties from minor-closed ones, which are closed under both vertex/edge deletions and contractions but form a stricter class—all minor-closed properties are hereditary, but the converse does not hold, as contractions can introduce structures absent in induced subgraphs alone. For instance, the property of being claw-free (no induced K1,3K_{1,3}) is hereditary but not minor-closed, since edge contractions may create claws. Examples of hereditary properties abound in structural graph theory. The class of edgeless graphs is hereditary, forbidden by the induced K2K_2 (a single edge). Bipartite graphs form a hereditary class, as they forbid all induced odd cycles of length at least 3. Chordal graphs, which admit perfect elimination orderings, are hereditary and characterized by the absence of induced cycles of length 4 or more. These examples illustrate how forbidden induced subgraphs provide a clean structural description, often leading to algorithmic or extremal insights. In applications, hereditary properties play a central role in structural graph theory, particularly in the study of . The Strong Perfect Graph Theorem establishes that a graph is —meaning its chromatic number equals its number for every —if and only if it contains no induced odd hole (cycle of length at least 5) or odd antihole. This underscores the significance of hereditary closure in resolving long-standing conjectures and enabling polynomial-time recognition algorithms for such classes.

Monotone Properties

In , a property PP of graphs is monotone increasing with respect to edges if, whenever a graph GG satisfies PP, then any supergraph of GG obtained by adding edges also satisfies PP; similarly, PP is monotone decreasing with respect to edges if any subgraph obtained by deleting edges from GG also satisfies PP. These properties can also be defined with respect to vertices, where adding or removing vertices (along with their incident edges) preserves the property, though edge-monotone variants are more commonly studied, particularly for properties like connectivity that depend primarily on edge structure. Many decision problems in that are NP-complete correspond to monotone properties; for instance, Hamiltonicity—the property of containing a Hamiltonian cycle—is monotone increasing, as adding edges to a Hamiltonian graph yields another Hamiltonian graph. Representative examples include connectivity, which is monotone increasing under edge addition (since adding edges cannot disconnect a connected graph), and acyclicity (being forest-like), which is monotone decreasing under edge addition (or equivalently, increasing under edge deletion, as adding edges can create cycles). Monotone properties play a central role in , where the goal is often to determine the maximum number of edges in a graph satisfying a monotone decreasing , such as avoiding a forbidden subgraph HH. provides the foundational result in this area, stating that the maximum number of edges in an nn-vertex graph without a complete subgraph KrK_r is achieved by the balanced complete (r−1)(r-1)-partite graph T(n,r−1)T(n, r-1), with ∣E(T(n,r−1))∣=(1−1r−1)n22+o(n2)\left| E(T(n, r-1)) \right| = \left(1 - \frac{1}{r-1}\right) \frac{n^2}{2} + o(n^2). This theorem, originally proved in 1941, exemplifies how monotone decreasing properties like KrK_r-freeness lead to precise extremal bounds and constructions. Hereditary properties, which are closed under deletion, form a subclass of edge- and vertex-monotone decreasing properties.

Graph Invariants

Definition and Role

In , a graph invariant is a function that assigns to each graph a value from a specified —such as the integers, real numbers, or other mathematical —such that isomorphic graphs receive identical values. This ensures the invariant depends solely on the of the graph, remaining unchanged under relabeling of vertices or other isomorphisms. Unlike general graph properties, which are typically binary and indicate whether a graph satisfies a yes/no condition (such as planarity or connectivity), graph invariants yield quantitative outputs that capture measurable aspects of the graph's structure. This quantitative nature allows invariants to provide finer-grained distinctions between non- graphs, serving as tools for partial isomorphism testing where equal invariant values suggest possible similarity but do not guarantee . A complete invariant, by contrast, fully resolves the problem: two graphs are if and only if their invariant values . Graph invariants play a central role in by enabling the classification and comparison of graphs without explicit isomorphism checks, which is computationally challenging. Basic examples include the order of a graph GG, defined as ∣V(G)∣|V(G)|, the number of vertices, and the , defined as ∣E(G)∣|E(G)|, the number of edges; both are preserved under and provide initial filters for distinguishing graphs. The development of graph invariants has paralleled efforts to address the since the early 20th century, with significant contributions from in his 1937 work on combinatorial enumeration, where invariants facilitated counting distinct graphs up to via group actions.

Computational Aspects

The of determining graph invariants varies widely, with some admitting efficient polynomial-time algorithms while others are NP-hard or worse. Efficient algorithms exist for several fundamental invariants. Connectivity, which measures whether a graph is connected or the number of its connected components, can be computed using (BFS) or (DFS), both running in O(|V| + |E|) time by traversing the graph from an arbitrary starting vertex and identifying reachable components. The , the longest shortest path between any pair of vertices, is also in P and can be found by running BFS from each vertex, yielding an O(|V|(|V| + |E|)) algorithm, though approximations or heuristics improve practicality for large graphs. For the chromatic number, which gives the minimum colors needed to color vertices without adjacent same-color pairs, exact computation is NP-hard, but the algorithm provides an approximation using at most Δ + 1 colors, where Δ is the maximum degree, by sequentially assigning the smallest available color to each vertex in a fixed order. Graph invariants play a key role in isomorphism testing, where the goal is to determine if two graphs are structurally identical up to relabeling. Many invariants, such as the degree sequence or , serve as quick heuristics: if they differ, the graphs are non-isomorphic, but equality does not confirm . The full (GI) problem was long open regarding its placement in P, but in 2015, László Babai announced a quasi-polynomial time running in exp(O((log n)^c)) time for some constant c, an improvement over subexponential bounds; subsequent refinements in 2017 and 2018 maintained this quasi-polynomial complexity without resolving it to strict polynomial time as of 2025. Recent advances leverage for approximating hard-to-compute invariants on large graphs. Graph neural networks (GNNs), which propagate node features through message-passing layers to produce permutation-invariant embeddings, have shown promise in estimating invariants like the clique number or by training on graph datasets, often achieving sublinear-time approximations that outperform traditional heuristics in scalability.
InvariantComplexity Class
ConnectivityP (O(
P (O(
Chromatic numberNP-hard

Examples

Structural Properties

Structural properties of graphs refer to qualitative characteristics that describe the arrangement and interconnections of vertices and edges, independent of numerical measures. These properties often determine whether a graph satisfies certain , connectivity, or partitioning conditions, and they are preserved under . Key examples include connectivity, planarity, bipartiteness, tree-like structures, and cycle-related traits such as being Eulerian or Hamiltonian, each with precise characterizations that facilitate algorithmic testing and theoretical analysis. Connectivity is a fundamental structural property indicating the robustness of a graph against vertex or edge removals. A graph is k-connected if it remains connected after removing any k-1 vertices, meaning there are at least k vertex-disjoint paths between any pair of non-adjacent vertices. This is formalized by , which states that in an undirected graph, the minimum number of vertices separating two non-adjacent vertices equals the maximum number of internally vertex-disjoint paths between them. Planarity describes whether a graph can be drawn in the plane without edge crossings. A graph is planar if and only if it contains no subgraph that is a subdivision of the K5K_5 or the K3,3K_{3,3}, as characterized by Kuratowski's theorem. For connected planar graphs, provides a relational constraint: if vv is the number of vertices, ee the number of edges, and ff the number of faces (including the outer face), then v−e+f=2.v - e + f = 2. This formula, originally derived for polyhedra, extends to planar embeddings and bounds the edge count, such as e≤3v−6e \leq 3v - 6 for simple planar graphs with v≥3v \geq 3. Bipartiteness is the property of partitioning vertices into two disjoint sets such that no two vertices within the same set are adjacent. A graph is bipartite if and only if it contains no odd-length cycles, a characterization that aligns with its 2-colorability. Bipartite graphs are hereditary, meaning subgraphs of bipartite graphs are also bipartite. In bipartite graphs, the maximum matching size equals the minimum vertex cover size, as given by König's theorem. Trees embody minimal connectivity without redundancy, defined as connected acyclic graphs. Equivalently, a tree on nn vertices has exactly n−1n-1 edges and features a unique path between any pair of vertices. The Prüfer code provides a bijection between labeled trees and sequences of length n−2n-2, enabling enumeration proofs like Cayley's formula. An Eulerian graph admits an Eulerian circuit, a closed that traverses each edge exactly once; for undirected graphs, this exists every vertex has even degree. A Hamiltonian graph admits a Hamiltonian cycle, a cycle visiting each vertex exactly once, though no simple characterization exists and determining Hamiltonicity is NP-complete. Both properties are structural and isomorphism-invariant but differ in computational tractability.

Numerical Invariants

Numerical invariants in are scalar values, typically integers or real numbers, that quantify structural features of a graph and remain unchanged under . Among the most fundamental are those derived from vertex degrees, which provide insights into connectivity and . The maximum degree, denoted Δ(G)\Delta(G), of a graph GG is the largest number of edges incident to any single vertex, serving as an upper bound on local connectivity. The degree, calculated as 2∣E∣/∣V∣2|E|/|V| where ∣E∣|E| is the number of edges and ∣V∣|V| is the number of vertices, measures the overall of the graph and equals half the sum of all vertex degrees by the , which states that ∑v∈Vdeg⁡(v)=2∣E∣\sum_{v \in V} \deg(v) = 2|E|. This lemma, a cornerstone of , follows from double-counting the incidences between vertices and edges and implies that the number of odd-degree vertices is even. The chromatic number χ(G)\chi(G) is the smallest number of colors needed to color the vertices of GG such that no adjacent vertices share the same color, quantifying the graph's colorability. Brooks' theorem provides a tight bound: for a connected graph GG that is neither complete nor an odd cycle, χ(G)≤Δ(G)\chi(G) \leq \Delta(G), with equality holding only for complete graphs KnK_{n} (where χ(Kn)=n=Δ(Kn)+1\chi(K_n) = n = \Delta(K_n) + 1 for n≥2n \geq 2) or odd cycles C2k+1C_{2k+1} (where χ(C2k+1)=3=Δ(C2k+1)+1\chi(C_{2k+1}) = 3 = \Delta(C_{2k+1}) + 1). This result, established in 1941, highlights exceptions where the chromatic number exceeds the maximum degree. Related invariants include the independence number α(G)\alpha(G), the size of the largest independent set (a set of vertices with no edges between them), and the clique number ω(G)\omega(G), the size of the largest clique (a complete subgraph). These provide lower and upper bounds on the chromatic number, respectively: χ(G)≥ω(G)\chi(G) \geq \omega(G) since each clique vertex requires a distinct color, and χ(G)≥∣V∣/α(G)\chi(G) \geq |V|/ \alpha(G) because the largest color class in any proper coloring has at most α(G)\alpha(G) vertices. Distance-based invariants capture global structure. The eccentricity of a vertex vv is the greatest shortest-path distance from vv to any other vertex. The diameter d(G)d(G) is the maximum eccentricity over all vertices, representing the longest shortest path in GG, while the radius r(G)r(G) is the minimum eccentricity, achieved at central vertices. Both can be computed using all-pairs shortest paths algorithms like Floyd-Warshall in O(∣V∣3)O(|V|^3) time or by running from each vertex in O(∣V∣(∣V∣+∣E∣))O(|V|(|V| + |E|)) time for unweighted graphs. A real-valued extension is the Wiener index W(G)=∑u,v∈Vd(u,v)W(G) = \sum_{u,v \in V} d(u,v), the sum of all pairwise shortest-path distances, originally introduced in 1947 for analyzing molecular structures in chemistry but now widely used in graph theory to measure compactness. For example, in a path graph PnP_n, W(Pn)=n(n2−1)6W(P_n) = \frac{n(n^2 - 1)}{6}.

Algebraic Invariants

Algebraic invariants in graph theory encompass matrix representations, polynomials, and sequences derived from a graph's structure, providing isomorphism-invariant encodings that capture global properties. The adjacency matrix A(G)A(G) of a simple undirected graph GG with vertex set V={v1,…,vn}V = \{v_1, \dots, v_n\} is the n×nn \times n symmetric matrix where Aij=1A_{ij} = 1 if {vi,vj}\{v_i, v_j\} is an edge, and 00 otherwise; its entries directly reflect the graph's connectivity, making it a foundational algebraic object. Similarly, the Laplacian matrix L(G)=D(G)−A(G)L(G) = D(G) - A(G) incorporates the degree matrix D(G)D(G), a diagonal matrix with DiiD_{ii} equal to the degree of viv_i; this operator-like matrix encodes diffusion processes on the graph and is positive semidefinite with smallest eigenvalue 00. The characteristic polynomial of the adjacency matrix, det⁡(xI−A(G))\det(xI - A(G)), yields the eigenvalues λ1≥λ2≥⋯≥λn\lambda_1 \geq \lambda_2 \geq \dots \geq \lambda_n, collectively termed the spectrum of GG, which is a multiset invariant under isomorphism and reveals structural features like connectivity and expansion. For the Laplacian, the spectrum consists of nonnegative eigenvalues with algebraic multiplicity of 00 equal to the number of connected components, facilitating analysis of cuts and flows. The chromatic polynomial P(G,k)P(G, k) counts the number of proper kk-colorings of GG, a monic polynomial of degree nn satisfying the deletion-contraction recurrence: for a non-loop edge ee, P(G,k)=P(G−e,k)−P(G/e,k)P(G, k) = P(G - e, k) - P(G / e, k), where G−eG - e deletes ee and G/eG / e contracts it; this recurrence enables recursive computation and links to matroid theory. Advanced algebraic invariants include the Ihara zeta function, defined as ζG(u)=∏P∈P(1−uℓ(P))−1\zeta_G(u) = \prod_{P \in \mathcal{P}} (1 - u^{\ell(P)})^{-1}, where P\mathcal{P} is the set of primitive, non-backtracking closed walks of length ℓ(P)\ell(P); it satisfies a determinant ζG(u)−1=(1−u2)r−1det⁡(I−Au+Qu2)\zeta_G(u)^{-1} = (1 - u^2)^{r-1} \det(I - A u + Q u^2), with rr the rank of the , AA the adjacency matrix, and QQ a diagonal matrix of excess degrees, connecting graph cycles to number-theoretic analogs. The matching polynomial α(G,x)=∑k=0⌊n/2⌋(−1)km(G,k)xn−2k\alpha(G, x) = \sum_{k=0}^{\lfloor n/2 \rfloor} (-1)^k m(G, k) x^{n-2k}, where m(G,k)m(G, k) counts kk-edge matchings, is another example, with real roots bounded by the graph's structural parameters and applications in dimer models. In , these invariants underpin partitioning algorithms, where the Fiedler vector (second smallest Laplacian eigenvector) guides balanced cuts by minimizing the , improving on random methods for sparse networks. Eigenvalue bounds, such as Alon's conjecture that for fixed d ≥ 3 and any ε > 0, sufficiently large random d-regular graphs have second-largest adjacency eigenvalue λ2 ≤ 2√(d-1) + ε, proven by in 2008, confirming optimal expansion for random regular graphs and impacting . Recent developments extend these invariants to quantum graph theory, where a generalized Euler characteristic derived from spectral traces serves as a new invariant for quantum graphs, experimentally verified via microwave networks, providing a topological invariant computable from the spectrum of low-lying eigenvalues. In network analysis, spectral methods via the Laplacian spectrum enable dynamic brain network partitioning in the SPARK toolbox, quantifying connectivity changes in EEG data for neuroscience applications post-2020.

References

  1. https://www.wisdom.weizmann.ac.il/~oded/PDF/pt-dense.pdf
  2. https://www.zib.de/userpage/groetschel/teaching/WS1314/BondyMurtyGTWA.pdf
  3. https://web.math.princeton.edu/~nalon/PDFS/monotone1.pdf
  4. https://web.math.princeton.edu/~nalon/PDFS/abbm3.pdf
  5. https://math.gordon.edu/courses/mat230/handouts/graphs.pdf
  6. http://www.math.uaa.alaska.edu/~afmaf/classes/math261/text/section-graph-isomorphism.html
  7. https://www3.nd.edu/~dgalvin1/60610/60610_S09/60610graphnotation.pdf
  8. https://mathworld.wolfram.com/IsomorphicGraphs.html
  9. https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Combinatorics_%28Morris%29/03%253A_Graph_Theory/11%253A_Basics_of_Graph_Theory/11.04%253A_Graph_Isomorphisms
  10. https://people.math.harvard.edu/~cmwang/teaching/55/4-23.pdf
  11. https://math.stackexchange.com/questions/1335035/what-is-graph-isomorphism-and-graph-invariant
  12. https://iuuk.mff.cuni.cz/~andrew/HomProfiles.pdf
  13. https://www.jstor.org/stable/2371086
  14. https://link.springer.com/content/pdf/10.1007/978-1-4684-8971-2.pdf
  15. https://www.cs.cmu.edu/~glmiller/Publications/Papers/Mi79.pdf
  16. https://people.math.binghamton.edu/zaslav/Tpapers/fis.pdf
  17. https://peeps.unet.brandeis.edu/~bernardi/publications/growth-minor-closed.pdf
  18. https://annals.math.princeton.edu/wp-content/uploads/annals-v164-n1-p02.pdf
  19. https://www.math.cmu.edu/~af1p/BOOK.pdf
  20. https://www.sciencedirect.com/science/article/pii/S0885064X97904507
  21. https://www.sciencedirect.com/science/article/pii/S0166218X01001755
  22. https://abelprize.no/sites/default/files/2021-09/Graph_invariants.pdf
  23. https://mathoverflow.net/questions/321696/graph-isomorphism-by-invariants
  24. https://cacm.acm.org/research/the-graph-isomorphism-problem/
  25. https://www.math.nagoya-u.ac.jp/~richard/teaching/s2024/SML_Wich_1.pdf
  26. https://link.springer.com/article/10.1007/BF02546665
  27. https://www.cs.cornell.edu/courses/cs3110/2012sp/recitations/rec21-graphs/rec21.html
  28. https://arxiv.org/abs/1512.03547
  29. https://people.cs.uchicago.edu/~laci/quasi25.pdf
  30. https://www.sciencedirect.com/science/article/pii/S2666651021000012
  31. https://arxiv.org/abs/1812.09902
  32. https://www.sciencedirect.com/science/article/abs/pii/S0304397521003042
  33. https://www.cs.cmu.edu/~avrim/Papers/coloring_worstcase.pdf
  34. http://matwbn.icm.edu.pl/ksiazki/fm/fm10/fm1012.pdf
  35. https://eudml.org/doc/212352
  36. https://scholarlycommons.pacific.edu/cgi/viewcontent.cgi?article=1229&context=euler-works
  37. http://people.cs.uchicago.edu/~razborov/teaching/HonorsDiscreteMath/notes17.pdf
  38. https://faculty.fiu.edu/~ramsamuj/graphtheory/chap8.pdf
  39. https://people.csail.mit.edu/virgi/diam.pdf
  40. https://mathworld.wolfram.com/WienerIndex.html
  41. https://link.springer.com/book/10.1007/978-1-4613-0163-9
  42. https://www.sciencedirect.com/science/article/pii/0024379594904863
  43. https://www.jstor.org/stable/1968214
  44. https://arxiv.org/abs/cs/0405020
  45. https://www.nature.com/articles/s41598-021-94331-0
  46. https://pmc.ncbi.nlm.nih.gov/articles/PMC12140659/
Add your contribution
Related Hubs
User Avatar
No comments yet.