A walk is a sequence , , , ..., of graph vertices and graph edges such that for , the edge has endpoints and (West 2000, p. 20). The length of a walk is its number of edges.A -walk is a walk with first vertex and last vertex , where and are known as the endpoints. Every -walk contains a -graph path (West 2000, p. 21).A walk is said to be closed if its endpoints are the same. The number of (undirected) closed -walks in a graph with adjacency matrix is given by , where denotes the matrix trace. In order to compute the number of -cycles, all closed -walks that are not cycles must be subtracted. Similarly, to compute the number of graph paths, all -walks that are not graph paths (because they contain redundant vertices) must be subtracted (cf. Festinger 1949, Ross and Harary 1952).For a simple graph (which has no multiple edges),a walk may be specified completely by an ordered list of vertices (West 2000, p. 20).A trail is a walk with no repeated edges...
The Königsberg bridge problem asks if the seven bridges of the city of Königsberg (left figure; Kraitchik 1942), formerly in Germany but now known as Kaliningrad and part of Russia, over the river Preger can all be traversed in a single trip without doubling back, with the additional requirement that the trip ends in the same place it began. This is equivalent to asking if the multigraph on four nodes and seven edges (right figure) has an Eulerian cycle. This problem was answered in the negative by Euler (1736), and represented the beginning of graph theory.On a practical note, J. Kåhre observes that bridges and no longer exist and that and are now a single bridge passing above with a stairway in the middle leading down to . Even so, there is still no Eulerian cycle on the nodes , , , and using the modern Königsberg bridges, although there is an Eulerian path (right figure). An example Eulerian path is illustrated in the right..
A circuit in which an entire graph is traversed in one route. Examples of curves that can be traced unicursally are the Mohammed sign and unicursal hexagram.The numbers of distinct unicursal polygrams that can be formed from points on circle with no two adjacent for , 2, ... are 1, 0, 0, 0, 1, 3, 23, 177, 1553, ... (OEIS A002816). For , these are given by the sumThis sequence is also given by the recurrence equation
The knight graph is a graph on vertices in which each vertex represents a square in an chessboard, and each edge corresponds to a legal move by a knight (which may only make moves which simultaneously shift one square along one axis and two along the other).The number of edges in the knight graph is (8 times the triangular numbers), so for , 2, ..., the first few values are 0, 0, 8, 24, 48, 80, 120, ... (OEIS A033996).Knight graphs are bipartite and therefore areperfect.The following table summarizes some named graph complements of knight graphs.-knight graph-queen graph-knight graph-queen graphThe knight graph is implemented in the Wolfram Language as KnightTourGraph[m, n], and precomputed properties are available in using GraphData["Knight", m, n].Closed formulas for the numbers of -graph cycles of the knight graph are given by for odd and(1)(E. Weisstein, Nov. 16, 2014).A knight's path is a sequence of moves by a..
The king graph is a graph with vertices in which each vertex represents a square in an chessboard, and each edge corresponds to a legal move by a king.The number of edges in the king graph is , so for , 2, ..., the first few values are 0, 6, 20, 42, 72, 110, ... (OEIS A002943).The order graph has chromatic number for and for . For , 3, ..., the edge chromatic numbers are 3, 8, 8, 8, 8, ....King graphs are implemented in the Wolfram Language as GraphData["King", m, n].All king graphs are Hamiltonian and biconnected. The only regular king graph is the -king graph, which is isomorphic to the tetrahedral graph . The -king graphs are planar only for (with the case corresponding to path graphs) and , some embeddings of which are illustrated above.The -king graph is perfect iff (S. Wagon, pers. comm., Feb. 22, 2013).Closed formulas for the numbers of -cycles of with are given by(1)(2)(3)(4)where the formula for appears in Perepechko and Voropaev.The..
A trail is a walk , , , ..., with no repeated edge. The length of a trail is its number of edges.A -trail is a trail with first vertex and last vertex , where and are known as the endpoints.A trail is said to be closed if its endpoints are the same.For a simple graph (which has no multiple edges),a trail may be specified completely by an ordered list of vertices (West 2000, p. 20).
A traceable graph is a graph that possesses a Hamiltonian path. Hamiltonian graphs are therefore traceable, but the converse is not necessarily true. The numbers of traceable graphs on , 2, ... are 1, 1, 2, 5, 18, 91, 734, ... (OEIS A057864), where the singleton graph is conventionally considered traceable. The first few are illustrated above, with a Hamiltonian path indicated in orange for each.Every self-complementary graph is traceable(Clapham 1974; Camion 1975; Farrugia 1999, p. 52).The following table lists some named graphs that are traceable but not Hamiltonian.graph theta-0 graph7Petersen graph10Herschel graph11Blanuša snarks18flower snark20Coxeter graph28double star snark30Tutte's graph46Szekeres snark50McLaughlin graph276
A graph is a hypotraceable graph if has no Hamiltonian path (i.e., it is not a traceable graph), but has a Hamiltonian path (i.e., is a traceable graph) for every (Bondy and Murty 1976, p. 61).There are no hypotraceable graphs on ten or fewer nodes (E. Weisstein, Dec. 11, 2013). In fact, the nonexistence of hypotraceable graphs on small numbers of vertices led T. Gallai to conjecture that no such graphs exist. This conjecture was refuted when a hypotraceable graph with 40 vertices was subsequently found by Horton (Grünbaum 1974, Thomassen 1974). Thomassen (1974) then showed that there exists a hypotraceable graph with vertices for , 37, 39, 40, and all . The smallest of these is the 34-vertex Thomassen graph (left figure above; Thomassen 1974; Bondy and Murty 1976, pp. 239-240).Walter (1969) gave an example of a connected graph in which the longest paths do not have a vertex in common, a property shared by hypotraceable..
An Eulerian path, also called an Euler chain, Euler trail, Euler walk, or "Eulerian" version of any of these variants, is a walk on the graph edges of a graph which uses each graph edge in the original graph exactly once. A connected graph has an Eulerian path iff it has at most two graph vertices of odd degree.
The conjecture that every cubic polyhedral graph is Hamiltonian. It was proposed by Tait in 1880 and refuted by Tutte (1946) with the counterexample on 46 vertices (Lederberg 1965) now known as Tutte's graph. Had the conjecture been true, it would have implied the four-color theorem.The following table summarizes some named counterexamples, illustrated above. The smallest examples known has 38 vertices (Lederberg 1965), and was apparently also discovered by D. Barnette and J. Bosák around the same time.graphreference38Barnette-Bośak-Lederberg graphLederberg (1965), Thomassen (1981), Grünbaum (2003, Fig. 17.1.5)42Faulkner-Younger graph 42Faulkner and Younger (1974)42Grinberg graph 42Faulkner and Younger (1974)44Faulkner-Younger graph 44Faulkner and Younger (1974)44Grinberg graph 44Sachs (1968), Berge (1973), Read and Wilson (1998, p. 274)46Grinberg graph 46Bondy..
An Eulerian graph is a graph containing an Eulerian cycle. The numbers of Eulerian graphs with , 2, ... nodes are 1, 1, 2, 3, 7, 15, 52, 236, ... (OEIS A133736), the first few of which are illustrated above.The corresponding numbers of connected Eulerian graphs are 1, 0, 1, 1, 4, 8, 37, 184, 1782, ... (OEIS A003049; Robinson 1969; Liskovec 1972; Harary and Palmer 1973, p. 117), the first few of which are illustrated above.Some care is needed in interpreting the term, however, since some authors define an Euler graph as a different object, namely a graph for which all vertices are of even degree (motivated by the following theorem). Euler showed (without proof) that a connected simple graph is Eulerian iff it has no graph vertices of odd degree (i.e., all vertices are of even degree). While the number of connected Euler graphs on nodes is equal to the number of connected Eulerian graphs on nodes, the counts are different for disconnected graphs since..
A Hamiltonian walk on a connected graph is a closed walk of minimal length which visits every vertex of a graph (and may visit vertices and edges multiple times). For example, a Hamiltonian walk on the above 3-pan graph is given by the vertex sequence 4, 3, 1, 2, 3, 4 and hence is of length 5.The length of a Hamiltonian walk in a graph is called the Hamiltonian number . A Hamiltonian graph has , where is the vertex count. A graph with is said to be almost Hamiltonian.
The Hamiltonian number of a connected graph is the length of a Hamiltonian walk . For a Hamiltonian graph, , where is the vertex count. The Hamiltonian number therefore gives one measure of how far away a graph is from being Hamiltonian, and a graph with is called an almost Hamiltonian graph.Punnim et al. (2007) show thatwith iff is a tree. Since a tree has Hamiltonian number , an almost Hamiltonian tree must satisfy , giving . Since the 3-path graph is the only tree on three nodes, it is also the only almost Hamiltonian tree.If is an almost Hamiltonian cubic graph with vertices, then the triangle-replaced graph has Hamiltonian number(Punnim et al. 2007).Values for special classes of graphs are summarized in the table below, where denotes the vertex count of the graphgraph generalized Petersen graph Hamiltonian graphtree..
The term "Euler graph" is sometimes used to denote a graph for which all vertices are of even degree (e.g., Seshu and Reed 1961). Note that this definition is different from that of an Eulerian graph, though the two are sometimes used interchangeably and are the same for connected graphs.The numbers of Euler graphs with , 2, ... nodes are 1, 1, 2, 3, 7, 16, 54, 243, 243, 2038, ... (OEIS A002854; Robinson 1969; Mallows and Sloane 1975; Buekenhout 1995, p. 881; Colbourn and Dinitz 1996, p. 687), the first few of which are illustrated above. There is an explicit formula giving these numbers.There are more Euler graphs than Eulerian graphs since there exist disconnected graphs having multiple disjoint cycles with each node even but for which no single cycle passes through all edges. The numbers of Euler-but-not-Eulerian graphs on , 2, ... nodes are 0, 0, 0, 0, 0, 1, 2, 7, 20, 76, 334, 2498, ... (OEIS A189771), the first few of which are..
A snake is an Eulerian path in the -hypercube that has no chords (i.e., any hypercube edge joining snake vertices is a snake edge). Klee (1970) asked for the maximum length of a -snake. Klee (1970) gave the bounds(1)for (Danzer and Klee 1967, Douglas 1969), as well as numerous references. Abbott and Katchalski (1988) show(2)and Snevily (1994) showed that(3)for , and conjectured(4)for . The first few values for for , 2, ..., are 2, 4, 6, 8, 14, 26, ... (OEIS A000937).
A Hamiltonian graph, also called a Hamilton graph, is a graph possessing a Hamiltonian cycle. A graph that is not Hamiltonian is said to be nonhamiltonian.A Hamiltonian graph on nodes has graph circumference .While it would be easy to make a general definition of "Hamiltonian" that goes either way as far as the singleton graph is concerned, defining "Hamiltonian" to mean "has a Hamiltonian cycle" and taking "Hamiltonian cycles" to be a subset of "cycles" in general would lead to the convention that the singleton graph is nonhamiltonian (B. McKay, pers. comm., Oct. 11, 2006). However, by convention, the singleton graph is generally considered to be Hamiltonian (B. McKay, pers. comm., Mar. 22, 2007). The convention in this work and in GraphData is that is Hamiltonian, while is nonhamiltonian.The numbers of simple Hamiltonian graphs on nodes for , 2, ... are..
Seymour conjectured that a graph of order with minimum vertex degree contains the th graph power of a Hamiltonian cycle, generalizing Pósa's Conjecture. Komlós et al. (1998) proved the conjecture for sufficiently large using Szemerédi's regularity lemma and a technique called the blow-up lemma.
One would think that by analogy with the matching-generating polynomial, independence polynomial, etc., a cycle polynomial whose coefficients are the numbers of cycles of length would be defined. While no such polynomial seems not to have been defined in the literature (instead, "cycle polynomials" commonly instead refers to a polynomial corresponding to cycle indices of permutation groups), they are defined in this work.The cycle polynomial, perhaps defined here for the first time, is therefore the polynomialwhose coefficients give the number of simple cycles present in a graph on nodes.Since the smallest possible cycle is of length 3, cycle polynomials have polynomial degree at least 3. The polynomial degree of is the girth of , and the graph is Hamiltonian iff the degree equals .In particular, gives the number of Hamiltonian cycles, so a graph is Hamiltonian iff . A graph is triangle-free iff , and square-free iff .Since cycle..
A chord of a graph cycle is an edge not in the edge set of whose endpoints lie in the vertex set (West 2000, p. 225). For example, in the diamond graph as labeled above, the edge is a chord of the cycle .A graph cycle possessing no chord is said to be a chordless cycle, and chordless cycles are important in the study and characterization of perfect graphs.A graph in which every graph cycle possesses a chord (i.e., in which no chordless cycles exists) is said to be a chordal graph. Similarly, a graph in which no chords exist is said to be a chordless graph.
The circuit rank , also denoted (Volkmann 1996, Babić et al. 2002) and known as the cyclomatic number, is the smallest number of graph edges which must be removed from a graph on graph edges and nodes such that no graph cycle remains. It is given by(1)for a graph with connected components.The circuit rank provides an inequality on the total number of undirected graph cycles given by(2)(Kirchhoff 1847, Ahrens 1897, König 1936, Volkmann 1996). Furthermore,(3)iff any two cycles have no edge in common (Volkmann 1996). Among connected graphs, the equality therefore holds for (and only for) cactus graphs. Mateti and Deo (1976) proved that there are "essentially" only four graphs with : the complete graphs and , the complete bipartite graph , and (Volkmann 1996).Unless otherwise stated, hydrogen atoms are usually ignored in the computation of such indices as organic chemists usually do when they write a benzene ring as a hexagon..
A Hamilton decomposition (also called a Hamiltonian decomposition; Bosák 1990, p. 123) of a Hamiltonian regular graph is a partition of its edge set into Hamiltonian cycles. The figure above illustrates the six distinct Hamilton decompositions of the pentatope graph .The definition is sometimes extended to a decomposition into Hamiltonian cycles for a regular graph of even degree or into Hamiltonian cycles and a single perfect matching for a regular graph of odd degree (Alspach 2010), with a decomposition of the latter type being known as a quasi-Hamilton decomposition (Bosák 1990, p. 123).For a cubic graph, a Hamilton decomposition is equivalent to a single Hamiltonian cycle. For a quartic graph, a Hamilton decomposition is equivalent to a Hamiltonian cycle , the removal of whose edges leaves a connected graph. When this connected graph exists, it gives the second of the pair of Hamiltonian cycles which together..
A chordless graph is a simple graph possessing no chords.A chordal graph (which possesses no chordless cycles) is not the same as (or converse of) a chordless graph (which possesses no chords). For example, the square graph is chordless but not chordal, the diamond graph and tetrahedral graph are chordal but not chordless, and empty graphs , path graphs , and the triangle graph are both chordal and chordless.The numbers of connected simple chordless graphs on , 2, ... nodes are 1, 1, 2, 4, 10, 27, ... (OEIS A287693), the first few of which are illustrated above.The numbers of not-necessarily connected simple chordless graphs on , 2, ... nodes are 1, 2, 4, 9, 21, 56, ... (OEIS A287694), the first few of which are illustrated above.
A chordless cycle of a graph is a graph cycle of length at least four in that has no cycle chord (i.e., the graph cycle is an induced subgraph). A chordal graph is a simple graph possessing no chordless cycles. A chordless cycle is sometimes also called a graph hole (Chvátal).A graph is perfect iff neitherthe graph nor its complement has a chordless cycle of odd order.If a chordless 5-cycle exists in a graph , one also exists in its graph complement since in the complement the interior diagonals are really edges in the original. In addition, if no 5-cycle exists in , then no chordless cycle exists in (S. Wagon,. pers. comm., Feb. 2013).No chordless cycles of length greater than exist in a graph with independence number .No chordless cycles of length greater than exist in the graph complement of a graph with , where is the clique covering number and is the clique number.Every cycle of a cactus graph is chordless, but there exist graphs..
The queen graph is a graph with vertices in which each vertex represents a square in an chessboard, and each edge corresponds to a legal move by a queen. The -queen graphs have nice embeddings, illustrated above. In general, the default embedding with vertices corresponding to squares of the chessboard has degenerate superposed edges, the only nontrivial exception being the -queen graph.Queen graphs are implemented in the Wolfram Language as GraphData["Queen", m, n].The following table summarized some special cases of queen graphs.namecomplete graph tetrahedral graph The following table summarizes some named graph complements of queen graphs.-queen graph-knight graph-queen graph-queen graph-knight graphAll queen graphs are Hamiltonian and biconnected. The only planar and only regular queen graph is the -queen graph, which is isomorphic to the tetrahedral graph .The only perfect queen graphs are , , and .A closed formula..
A chordal graph is a simple graph in which every graph cycle of length four and greater has a cycle chord. In other words, a chordal graph is a graph possessing no chordless cycles.The numbers of simple chordal graphs on , 2, ... nodes are 1, 2, 4, 10, 27, 94, 393, ... (OEIS A048193). The first few are illustrated above, though many are trivially chordal since they possess no cycles of length .The corresponding numbers of simple connected chordal graphs are 1, 1, 2, 5, 15, 58, 272, ... (OEIS A048192). The first few are illustrated above, though many are again chordal only trivially.A split graph is a simple graph whose vertices can be partitioned into a clique and an independent (stable) set. Split graphs are a special class of chordal graphs (Brandstadt et al. 1999).Every chordal graph is perfect.It is possible to recognize chordal graphs in linear time. Furthermore, a maximum clique of a chordal graph can be found in polynomial time although the problem..
A pseudotree is a connected pseudoforest, i.e., an undirected connected graph that contains at most one graph cycle. Connected acyclic graphs (i.e., trees), are therefore pseudotrees.Some care is needed when encountering pseudotrees as some authors use the term to mean "a pseudotree that is not a tree." Such graphs are perhaps better known as connected unicyclic graphs for clarity.The numbers of pseudotrees on 1, 2, 3, ... vertices are 1, 1, 2, 4, 8, 19, 44, 112, ... (OEIS A005703), the first few of which are illustrated above.
A pseudoforest is an undirected graph in which every connected component contains at most one graph cycle. A pseudotree is therefore a connected pseudoforest and a forest (i.e., not-necessarily-connected acyclic graph) is a trivial pseudoforest.Some care is needed when encountering pseudoforests as some authors use the term to mean "a pseudoforest that is not a forest."The numbers of pseudoforests on 1, 2, 3, ... vertices are 1, 2, 4, 9, 19, 46, 108, 273 ... (OEIS A134964), the first few of which are illustrated above.
There are several related theorems involving Hamiltoniancycles of graphs that are associated with Pósa.Let be a simple graph with graph vertices. 1. If, for every in , the number of graph vertices of vertex degree not exceeding is less than , and 2. If, for odd, the number of graph vertices with vertex degree not exceeding is less than or equal to , then contains a Hamiltonian cycle.Kronk (1969) generalized this result as follows. Let be a simple graph with graph vertices, and let . Then the following conditions are sufficient for to be -line Hamiltonian: 1. For all integers with , the number of graph vertices of vertex degree not exceeding is less than , 2. The number of points of degree not exceeding does not exceed . Pósa (1963) generalized a result of Dirac by proving that every finite simple graph with a sufficiently large valencies of all (or, in some cases, of almost all) vertices and with a sufficiently large number of vertices satisfies..
A formula satisfied by all Hamiltonian cycles with nodes. Let be the number of regions inside the circuit with sides, and let be the number of regions outside the circuit with sides. If there are interior diagonals, then there must be regions(1)Any region with sides is bounded by graph edges, so such regions contribute to the total. However, this counts each diagonal twice (and each graph edge only once). Therefore,(2)Take (2) minus (1),(3)Similarly,(4)so(5)
Dirac (1952) proved that if the minimum vertex degree for a graph on nodes, then contains a Hamiltonian cycle (Bollobás 1978, Komlós et al. 1996).In 1962, Pósa conjectured that contains a square of a Hamiltonian cycle if (Erdős 1964, p. 159; Komlós et al. 1996), where a graph contains the square of a Hamiltonian cycle if there is a Hamiltonian cycle such that , for , 2, ..., .Komlós et al. (1996) proved that there exists a natural number such that if a graph has order and minimum vertex degree at least , then contains the square of a Hamiltonian cycle. This proved Pósa's conjecture (Erdős 1964) for sufficiently large . Kierstead and Quintana (1998) proved Pósa's conjecture for graphs containing a 4-clique .The conjecture was generalized by Seymour (1974) to state that if , then contains the th power of a Hamiltonian cycle (Komlós et al. 1996)...
A path in a graph is a subgraph of that is a path graph (West 2000, p. 20).An -path is a path whose endpoints (vertices of degree 1) are the vertices with indices and . (The symbols and are also commonly used.) A single -path may be found in the Wolfram Language using FindPath[g, s, t], while FindPath[g, s, t, kspec, n] finds at most paths of length kspec (where kspec may be Infinity and may be All).The length of a path is the number of edges it contains.For a simple graph, a path is equivalent to a trail and is completely specified by an ordered sequence of vertices. For a simple graph , a Hamiltonian path is a path that includes all vertices of (and whose endpoints are not adjacent).The number of (undirected) -walks from vertex to vertex in a graph with adjacency matrix is given by the element of (Festinger 1949). In order to compute the number of graph paths, all closed -walks that are not paths must be subtracted. The first few matrices of -paths can be given..
A planar hypotraceable graph is a hypotraceable graph that is also planar. A number of planar hypotraceable graphs are illustrated above.Using a theorem of Thomassen (1974), the Wiener-Araya graph on 42 vertices can be used to construct a planar hypotraceable graph on 162 vertices, smaller than the 186-vertex graph obtained from the 48-Zamfirescu graph using Thomassen's construction. These graphs are implemented in the Wolfram Language as GraphData["PlanarHypohamiltonian", 162] and GraphData["PlanarHypohamiltonian", 186], respectively.Jooyandeh et al. (2017) showed that there exist planar hypotraceable graphson 154 vertices, as well as on all vertex counts greater than or equal to 156.Using the 70-node Araya-Wiener graph, a 340-nodecubic planar hypotraceable graph can be constructed (Araya and Wiener 2011).Holton and Sheehan (1993) asked if there exists an integer such that a cubic planar hypotraceable..
An alternative name for a chordless cycle, often simply called a "hole" (Chvátal). Graph holes are called even if they have an even number of vertices and odd if they have an odd number of vertices. The graph complement of a hole is called a graph antihole. No odd hole is a perfect graph (since the clique number of an odd hole is 2 and its chromatic number is 3).
One would think that by analogy with the matching-generating polynomial, independence polynomial, etc., a path polynomial whose coefficients are the numbers of paths of length would be defined. While no such polynomial seems not to have been defined in the literature, they are defined in this work.The path polynomial, perhaps defined here for the first time, is therefore the polynomialwhose coefficients give the number of simple paths of length present in a graph on nodes.Since the smallest possible path is of length 1, path polynomials have polynomial degree at least 1. In particular, , where is the edge count of a graph .A graph is traceable iff the degree of the path polynomial equals . In particular, gives the number of Hamiltonian paths, so a graph is traceable iff .Since path counts in a disconnected graph are the sum of path counts in its connected components, the path polynomial is additive over connected components...
A cycle of a graph , also called a circuit if the first vertex is not specified, is a subset of the edge set of that forms a path such that the first node of the path corresponds to the last. A maximal set of edge-disjoint cycles of a given graph can be obtained using ExtractCycles[g] in the Wolfram Language package Combinatorica` .A cycle that uses each graph vertex of a graphexactly once is called a Hamiltonian cycle.A graph containing no cycles of length three is called a triangle-free graph, and a graph containing no cycles of length four is called a square-free graph.A graph containing no cycles of any length is known as an acyclic graph, whereas a graph containing at least one cycle is called a cyclic graph. A graph possessing exactly one (undirected, simple) cycle is called a unicyclic graph. A connected acyclic graph is known as a tree, and a possibly disconnected acyclic graph is known as a forest.The length of the shortest graph cycle (if any) in a given..
Barnette's conjecture asserts that every 3-connected bipartite cubic planar graph is Hamiltonian. The only graph on nine or fewer vertices satisfying Barnette's conditions is the cubical graph, which is indeed Hamiltonian. The skeletons of the truncated octahedron, great rhombicuboctahedron, and great rhombicosidodecahedron also satisfy the conditions and, since they are Archimedean solids, are indeed Hamiltonian. Holton et al. (1985) proved that all graphs having fewer than 66 vertices satisfy the conjecture, but the general conjecture remains open.Similarly, Barnette conjectured that all cubic, 3-connected, planar graphs with a face size of at most 6 are Hamiltonian. Aldred et al. (2000) have verified this conjecture for all graphs with fewer than 177 vertices.
The graph complement of a graph hole. Graph antiholes are called even if they have an even number of vertices and odd if they have an odd number of vertices (Chvátal). No odd antihole is a perfect graph (since the clique number of an antihole with vertices is and its chromatic number is ).
A simple unlabeled graph on vertices is called pancyclic if it contains cycles of all lengths, 3, 4, ..., . Since they must contain a cycle of length , pancyclic graphs are Hamiltonian.The numbers of pancyclic graphs on , 2, ... vertices are 0, 0, 1, 2, 7, 43, 372, 6132, 176797, 9302828, ... (OEIS A286684), the first few of which are illustrated above.
The length of the shortest graph cycle (if any) in a graph. Acyclic graphs are considered to have infinite girth (Skiena 1990, p. 191). The girth of a graph may be found using Girth[g] in the Wolfram Language package Combinatorica` . Precomputed girths for many named graphs can be obtained using GraphData[graph, "Girth"].The following table gives examples of graphs with various girths.girthexample3tetrahedral graph, complete graph 4cubical graph, utility graph5Petersen graph6Heawood graph7McGee graph8Levi graph
If a graph has graph vertices such that every pair of the graph vertices which are not joined by a graph edge has a sum of valences which is , then is Hamiltonian.A graph satisfying Ore's criterion is known as an Ore graph.
There are several definitions of "almost Hamiltonian" in use.As defined by Punnim et al. (2007), an almost Hamiltonian graph is a graph on nodes having Hamiltonian number .As defined by Sanders (1987), a graph with vertices is almost Hamiltonian if every subset of vertices is contained in a circuit, a definition which is similar to that for a maximally nonhamiltonian graph.This work adopts the definition of Punnim et al. (2007). The numbers of almost Hamiltonian graphs of this type on , 2, ... vertices are 0, 0, 1, 1, 7, 28, 257, 2933, ... (OEIS A185360), the first few of which are illustrated above.Punnim et al. (2007) showed that the generalized Petersen graph is almost Hamiltonian iff and .Punnim et al. (2007) proved that there exists an almost Hamiltonian cubic graph for every even order . The Petersen graph is the unique almost Hamiltonian cubic graph on 10 vertices, and Tietze's graph is the unique almost Hamiltonian cubic graph on..
The Markström graph is a cubic planar graph on 24 vertices which lacks cycles of length 4 and 8 but contains cycles of length 16. (In particular, it contains cycles of lengths 3, 5, 6, 7, and 9-24.)This graph is related to the open Erdős-Gyárfás conjecture, which posits that any graph with minimum vertex degree 3 contains a simple cycle whose length is a power of two. Gordon Royle and Klas Markström showed that any counterexample must have at least 17 vertices and that any cubic counterexample must have at least 30 vertices. Markström found four graphs on 24 vertices in which the only power-of-two cycles has 16 vertices; the Markström graph is the only planar graph of these four.
A forest is an acyclic graph (i.e., a graph without any graph cycles). Forests therefore consist only of (possibly disconnected) trees, hence the name "forest."Examples of forests include the singleton graph,empty graphs, and all trees.A forest with components and nodes has graph edges. The numbers of forests on , 2, ... nodes are 1, 2, 3, 6, 10, 20, 37, ... (OEIS A005195).A graph can be tested to determine if it is acyclic (i.e., a forest) in the Wolfram Language using AcylicGraphQ[g]. A collection of acyclic graphs is available as GraphData["Acyclic"] or GraphData["Forest"].The total numbers of trees in all the forests of orders , 2, ... are 1, 3, 6, 13, 24, 49, 93, 190, 381, ... (OEIS A005196). The average numbers of trees are therefore 1, 3/2, 2, 13/6, 12/5, 49/20, 93/37, 5/2, ... (OEIS A095131 and A095132).The triangle of numbers of -node forests containing trees is 1; 1, 1; 1, 1, 1; 2, 2, 1, 1; 3, 3, 2, 1, 1; ... (OEIS..
An acyclic graph is a graph having no graph cycles.Acyclic graphs are bipartite.A connected acyclic graph is known as a tree, and a possibly disconnected acyclic graph is known as a forest (i.e., a collection of trees).The numbers of acyclic graphs (forests) on , 2, ... are 1, 2, 3, 6, 10, 20, 37, 76, 153, ... (OEIS A005195), and the corresponding numbers of connected acyclic graphs (trees) are 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, ... (OEIS A000055).A graph can be tested in the Wolfram Language to see if it is acyclic using AcyclicGraphQ[g], and a collection of acyclic graphs are available as GraphData["Acyclic"].A graph with a single cycle is known as a unicyclicgraph.
The singleton graph is the graph consisting of a single isolated node with no edges. It is therefore the empty graph on one node. It is commonly denoted (i.e., the complete graph on one node).By convention, the singleton graph is considered to be Hamiltonian(B. McKay, pers. comm., Mar. 22, 2007).
A matchstick graph is a simple graph which has a graph embedding that is planar, for which all distances between vertices have unit distance, and which is non-degenerate (so no vertices are coincident, no edges cross or overlap, and no vertices are coincident with edges on which they are not incident).A matchstick graph is therefore both planar and unit-distance, but a planar unit-distance graph may fail to be a matchstick graph if a single embedding cannot be constructed having both properties. Examples include the prism graphs and Moser spindle, with the sole 6-vertex connected planar unit-distance non-matchstick graph being the 3-prism graph . The numbers of connected graphs on , 2, ... vertices that are planar and unit-distance but not matchstick are 0, 0, 0, 0, 0, 1, 13, ... (E. Weisstein, Apr. 30, 2018), where the 7-vertex examples are illustrated above.The numbers of connected matchstick graphs on , 2, ... nodes are 1, 1, 2,..
Two nonisomorphic graphs can share the same graph spectrum, i.e., have the same eigenvalues of their adjacency matrices. Such graphs are called cospectral. For example, the graph union and star graph , illustrated above, both have spectrum (Skiena 1990, p. 85). This is the smallest pair of simple graphs that are cospectral. Determining which graphs are uniquely determined by their spectra is in general a very hard problem.Only a small fraction of graphs are known to be so determined, but it is conceivablethat almost all graphs have this property (van Dam and Haemers 2002).In the Wolfram Language, graphs knownto be determined by their spectra are identified as GraphData["DeterminedBySpectrum"].The numbers of simple graphs on , 2, ... nodes that are determined by spectrum are 1, 2, 4, 11, 32, 146, 934, 10624, 223629, ... (OEIS A178925), while the corresponding numbers not determined by spectrum are 0, 0, 0, 0, 2, 10, 110, 1722,..
A -regular simple graph on nodes is strongly -regular if there exist positive integers , , and such that every vertex has neighbors (i.e., the graph is a regular graph), every adjacent pair of vertices has common neighbors, and every nonadjacent pair has common neighbors (West 2000, pp. 464-465). A graph that is not strongly regular is said to be weakly regular.The complete graph is strongly regular for all . The status of the trivial singleton graph is unclear. Opinions differ on if is a strongly regular graph, though since it has no well-defined parameter, it is preferable to consider it not to be strongly regular (A. E. Brouwer, pers. comm., Feb. 6, 2013).The graph complement of a non-empty non-complete strongly regular graph with parameters is another strongly regular graph with parameters .A number of strongly regular graphs are implemented in the WolframLanguage as GraphData["StronglyRegular"].The..
The Harborth graph is the smallest known 4-regular matchstick graph. It is therefore both planar and unit-distance. It has 104 edges and 52 vertices. This graph was named after its discoverer H. Harborth, who first presented it to a general public in 1986 (Harborth 1994, Petersen 1996, Gerbracht 2006).The Harborth graph is implemented in the WolframLanguage as GraphData["HarborthGraph"].Analytic expressions for the vertices consisting of algebraic numbers of degree 22 (with large coefficients) were derived by Gerbracht (2006). As a consequence, Gerbracht (2006) also proved that the Harborth graph is rigid.
A snark is a connected bridgeless cubic graph (i.e., a biconnected cubic graph) with edge chromatic number of four. (By Vizing's theorem, the edge chromatic number of every cubic graph is either three or four, so a snark corresponds to the special case of four.) Snarks are therefore class 2 graphs.In order to avoid trivial cases, snarks are commonly restricted to be connected (so that the graph union of two Petersen graphs is excluded), have girth 5 or more and not to contain three edges whose deletion results in a disconnected graph, each of whose components is nontrivial (Read and Wilson 1998, p. 263).Snarks that are trivial in the above senses are sometimes called "reducible" snarks. A number of reducible snarks are illustrated above.The Petersen graph is the smallest snark, and Tutte conjectured that all snarks have Petersen graph graph minors. This conjecture was proven in 2001 by Robertson, Sanders, Seymour, and Thomas,..
The maximum leaf number of a graph is the largest number of tree leaves in any of its spanning trees.The maximum leaf number and connected domination number of a graph are connected bywhere is the vertex count of .Many families of graphs have simple closed forms, as summarized in the following table. In the table, denotes the floor function.graph familymaximum leaf numberAndrásfai graphantiprism graphApollonian networkbarbell graphblack bishop graph book graph cocktail party graph complete bipartite graph complete bipartite graph complete graph complete tripartite graph complete tripartite graph -crossed prism graphcrown graph cycle graph 2gear graphhelm graphladder graph Möbius ladder pan graph3path graph 2prism graph rook complement graph rook graph star graph sun graphsunlet graph triangular graphweb graphwheel graph white bishop graph ..
A tree in which each non-leaf graph vertex has a constant number of branches is called an -Cayley tree. 2-Cayley trees are path graphs. The unique -Cayley tree on nodes is the star graph. The illustration above shows the first few 3-Cayley trees (also called trivalent trees, binary trees, or boron trees). The numbers of binary trees on , 2, ... nodes (i.e., -node trees having vertex degree either 1 or 3; also called 3-Cayley trees, 3-valent trees, or boron trees) are 1, 1, 0, 1, 0, 1, 0, 1, 0, 2, 0, 2, 0 ,4, 0, 6, 0, 11, ... (OEIS A052120).The illustrations above show the first few 4-Cayley and 5-Cayley trees.The percolation threshold for a Cayley tree having branches is
For a given positive integer , does there exist a weighted tree with graph vertices whose paths have weights 1, 2, ..., , where is a binomial coefficient? Taylor showed that no such tree can exist unless it is a perfect square or a perfect square plus 2. No such trees are known except , 3, 4, and 6.Székely et al. showed computationally that there are no such trees with and 11. They also showed that if there is such a tree on vertices then the maximum vertex degree is at most and that there is no path of length larger than . They conjecture that there are only finitely many such trees.
A caterpillar graph, caterpillar tree, or simply "caterpillar," is a tree in which every graph vertex is on a central stalk or only one graph edge away from the stalk (in other words, removal of its endpoints leaves a path graph; Gallian 2007). A tree is a caterpillar iff all nodes of degree are surrounded by at most two nodes of degree two or greater.Caterpillar graphs are graceful.The number of caterpillar trees on nodes iswhere is the floor function (Harary and Schwenk 1973). For , 2, ... nodes, this gives 1, 1, 1, 2, 3, 6, 10, 20, 36, 72, 136, ... (OEIS A005418). The first few caterpillars are illustrated above.The number of noncaterpillar trees on , 8, ... as 1, 3, 11, 34, 99, ... (OEIS A052471). The noncaterpillar trees on nodes are illustrated above.
A strongly binary tree is a rooted tree for which the root is adjacent to either zero or two vertices, and all non-root vertices are adjacent to either one or three vertices (Finch 2003, p. 298). The numbers of strongly binary trees on , 2, ... nodes are 1, 0, 1, 0, 1, 0, 2, 0, 3, 0, 6, 0, ... (OEIS A001190). The counts are 0 for even, and for odd , where is the number of weakly binary trees on nodes (Finch 2003, p. 298).
A tree with its nodes labeled. The number of labeled trees on nodes is , the first few values of which are 1, 1, 3, 16, 125, 1296, ... (OEIS A000272). Cayley (1889) provided the first proof of the number of labeled trees (Skiena 1990, p. 151), and a constructive proof was subsequently provided by Prüfer (1918). Prüfer's result gives an encoding for labeled trees known as Prüfer code (indicated underneath the trees above, where the trees are depicted using an embedding with root at the node labeled 1).The probability that a random labeled tree is centeredis asymptotically equal to 1/2 (Szekeres 1983; Skiena 1990, p. 167).
The Steiner tree of some subset of the vertices of a graph is a minimum-weight connected subgraph of that includes all the vertices. It is always a tree. Steiner trees have practical applications, for example, in the determination of the shortest total length of wires needed to join some number of points (Hoffman 1998, pp. 164-165).The determination of a Steiner tree is NP-complete and hard even to approximate. There is 1.55-approximate algorithm due to Robins and Zelikovski (2000), but approximation within 95/94 is known to be NP-hard (Chlebik and Chlebikova 2002).
An algorithm for finding a graph's spanning tree of minimum length. It sorts the edges of a graph in order of increasing cost and then repeatedly adds edges that bridge separate components until the graph is fully connected (Pemmaraju and Skiena 2003, p. 336). By negating the weights for each edge, the algorithm can also be used to find a maximum spanning tree.Kruskal's algorithm is implemented in the Wolfram Language as FindSpanningTree[g, Method -> "Kruskal"].
A binary tree is a tree-like structure that is rooted and in which each vertex has at most two children and each child of a vertex is designated as its left or right child (West 2000, p. 101). In other words, unlike a proper tree, the relative positions of the children is significant.Dropping the requirement that left and right children are considered unique gives a true tree known as a weakly binary tree (in which, by convention, the root node is also required to be adjacent to at most one graph vertex).The height of a binary tree is the number of levels within the tree. The numbers of binary trees of height , 2, ... nodes are 1, 3, 21, 651, 457653, ... (OEIS A001699). A recurrence equation giving these counts is(1)with .The number of binary trees with nodes are 1, 2, 5, 14, 42, ... (OEIS A000108), which are the Catalan number .For a binary tree of height with nodes,(2)These extremes correspond to a balanced tree (each node except the tree leaves has a left..
A spanning tree of a graph on vertices is a subset of edges that form a tree (Skiena 1990, p. 227). For example, the spanning trees of the cycle graph , diamond graph, and complete graph are illustrated above.The number of nonidentical spanning trees of a graph is equal to any cofactor of the degree matrix of minus the adjacency matrix of (Skiena 1990, p. 235). This result is known as the matrix tree theorem. A tree contains a unique spanning tree, a cycle graph contains spanning trees, and a complete graph contains spanning trees (Trent 1954; Skiena 1990, p. 236). A count of the spanning trees of a graph can be found using the command NumberOfSpanningTrees[g] in the Wolfram Language package Combinatorica` . For a connected graph, it is also given bywhere is the Tutte polynomial.Kruskal's algorithm can be used to find a maximum or minimum spanning tree of graph.The following table summarizes the numbers of spanning trees for various..
An -banana tree, as defined by Chen et al. (1997), is a graph obtained by connecting one leaf of each of copies of an -star graph with a single root vertex that is distinct from all the stars.Banana trees are graceful (Sethuraman and J. Jesintha2009, Gallian 2018).The -banana tree has rank polynomialPrecomputed properties of a number of banana trees is implemented in the Wolfram Language as GraphData["BananaTree", n, k].
A graph is said to be locally , where is a graph (or class of graphs), when for every vertex , the graph induced on by the set of adjacent vertices of (sometimes called the ego graph in more recent literature) is isomorphic to (or to a member of) . Note that the term "neighbors" is sometimes used instead of "adjacent vertices" here (e.g., Brouwer et al. 1989), so care is needed since the definition of local graphs excludes the vertex on which a subgraph is induced, while the definitions of graph neighborhood and neighborhood graph include itself.For example, the only locally pentagonal (cycle graph ) graph is the icosahedral graph (Brouwer et al. 1989, p. 5).The following table summarizes some named graphs that have named local graphs.graphlocal graph24-cell graphcubical graphcocktail party graph 16-cell graphcocktail party graph cocktail party graph complete graph complete graph complete -partite graph complete..
LCF notation is a concise and convenient notation devised by Joshua Lederberg (winner of the 1958 Nobel Prize in Physiology and Medicine) for the representation of cubic Hamiltonian graphs (Lederberg 1965). The notation was subsequently modified by Frucht (1976) and Coxeter et al. (1981), and hence was dubbed "LCF notation" by Frucht (1976). Pegg (2003) used the notation to describe many of the cubic symmetric graphs. The notation only applies to Hamiltonian graphs, since it achieves its symmetry and conciseness by placing a Hamiltonian cycle in a circular embedding and then connecting specified pairs of nodes with edges.For example, the notation describes the cubical graph illustrated above. To see how this works, begin with the cycle graph . Beginning with a vertex , count three vertices clockwise () to and connect it to with an edge. Now advance to , count three vertices counterclockwise () to vertex , and connect and with an edge...
Let denote the domination number of a simple graph . Then Vizing (1963) conjectured thatwhere is the graph product. While the full conjecture remains open, Clark and Suen (2000) have proved the looser result
Let be a simple connected graph, and take , where is the graph diameter. Then has global parameters (respectively , ) if the number of vertices at distance (respectively, , ) from a given vertex that are adjacent to a vertex at distance from is the constant (respectively , ) depending only on (i.e., not on of ).Global parameters may be computed by the GRAPE package in GAP using the function GlobalParameters(G), which returns a list of length whose th element is the list (except that if some global parameter does not exist then is put in its place). Note that is a distance-regular graph iff this function returns no in place of a global parameter.A distance-regular graph with global parameters has intersection array .
Let denote the set of all vertices lying on an -graph geodesic in , then a set with is called a geodetic set in and is denoted .
The degree of a graph vertex of a graph is the number of graph edges which touch . The vertex degrees are illustrated above for a random graph. The vertex degree is also called the local degree or valency. The ordered list of vertex degrees in a given graph is called its degree sequence. A list of vertex degrees of a graph can be computed in the Wolfram Language using VertexDegree[g], and precomputed vertex degrees are available for particular embeddings of many named graphs via GraphData[graph, "VertexDegrees"].The minimum vertex degree in a graph is denoted , and the maximum vertex degree is denoted (Skiena 1990, p. 157).The graph vertex degree of a point in a graph, denoted , satisfieswhere is the total number of graph edges.Directed graphs have two types of degrees, knownas the indegree and the outdegree...
An unordered pair representation is a representation of an undirected graph in which edges are specified as unordered pairs of vertex indices. The unordered pairs representation of an undirected graph may be computed in the Wolfram Language using List @@@ EdgeList[g], and a graph may be constructed from an unordered pair representation using Graph[UndirectedEdge @@@ l].
Let graph have points and graph have points , where . Then if for each , the subgraphs and are isomorphic, then the graphs and are isomorphic.
Two graphs which contain the same number of graph vertices connected in the same way are said to be isomorphic. Formally, two graphs and with graph vertices are said to be isomorphic if there is a permutation of such that is in the set of graph edges iff is in the set of graph edges .Canonical labeling is a practically effective technique used for determining graph isomorphism. Several software implementations are available, including nauty (McKay), Traces (Piperno 2011; McKay and Piperno 2013), saucy, and bliss, where the latter two are aimed particularly at large sparse graphs.The equivalence or nonequivalence of two graphs can be ascertained in the Wolfram Language using the command IsomorphicGraphQ[g1, g2].Determining if two graphs are isomorphic is thought to be neither an NP-complete problem nor a P-problem, although this has not been proved (Skiena 1990, p. 181). In fact, there is a famous complexity class called graph isomorphism..
The sum over all external (square) nodes of the lengths of the paths from the root of an extended binary tree to each node. For example, in the tree above, the external path length is 25 (Knuth 1997, pp. 399-400). The internal and external path lengths are related bywhere is the number of internal nodes.
Tutte (1971/72) conjectured that there are no 3-connected nonhamiltonian bicubic graphs. However, a counterexample was found by J. D. Horton in 1976 (Gropp 1990), and several smaller counterexamples are now known.Known small counterexamples are summarized in the following table and illustrated above.namereference50Georges graphGeorges (1989), Grünbaum (2006, 2009)54Ellingham-Horton 54-graphEllingham and Horton (1983)78Ellingham-Horton 78-graphEllingham (1981, 1982)78Owens graphOwens (1983)92Horton 92-graphHorton (1982)96Horton 96-graphBondy and Murty (1976)
The intersection number of a given graph is the minimum number of elements in a set such that is an intersection graph on .
Given a distance-regular graph with integers such that for any two vertices at distance , there are exactly neighbors of and neighbors of , the sequenceis called the intersection array of .A similar type of intersection array can also be defined for a distance-transitivegraph.A distance-regular graph with global parameters has intersection array .
The theorem, originally conjectured by Berge (1960, 1961), that a graph is perfect iff neither the graph nor its graph complement contains an odd graph cycle of length at least five as an induced subgraph became known as the strong perfect graph conjecture (Golumbic 1980; Skiena 1990, p. 221). The conjecture can be stated more simply as the assertion that a graph is perfect iff it contains no odd graph hole and no odd graph antihole. The proposition can be stated even more succinctly as "a graph is perfect iff it is a Berge graph."This conjecture was proved in May 2002 following a remarkable sequence of results by Chudnovsky, Robertson, Seymour, and Thomas (Cornuéjols 2002, MacKenzie 2002).
The sum over all internal (circular) nodes of the paths from the root of an extended binary tree to each node. For example, in the tree above, the internal path length is 11 (Knuth 1997, pp. 399-400). The internal and external path lengths are related bywhere is the number of internal nodes.
An integral graph is defined as a graph whose graph spectrum consists entirely of integers. The notion was first introduced by Harary and Schwenk (1974). The numbers of simple integral graphs on , 2, ... nodes are 0, 2, 3, 6, 10, 20, 33, 71, ... (OEIS A077027), illustrated above for small .The numbers of connected simple integral graphs on , 2, ... nodes are 1, 1, 1, 2, 3, 6, 7, 22, 24, 83, ... (OEIS A064731), illustrated above for small .The following table lists common graph classes and the their members which are integral.graphintegral for of the formantiprism graph3complete graph allcycle graph 2, 3, 4, 6empty graphallprism graph3, 4, 6star graph wheel graph 4The following table lists some special named graphs that are integral and gives their spectra.graphgraph spectrum16-cell24-cellClebsch graphcubical graphcuboctahedral graphDesargues graphHall-Janko graphHoffman graphHoffman-Singleton graphLevi graphM22 graphMcLaughlin..
The edge set of a graph is simply a set of all edges of the graph. The cardinality of the edge set for a given graph is known as the edge count of .The edge set for a particular graph embedding of a graph is given in the Wolfram Language by EdgeList[g]. The edge pairs for many named graphs can be given by the command GraphData[graph, "EdgeIndices"].
Let a set of vertices in a connected graph be called convex if for every two vertices , the vertex set of every graph geodesic lies completely in . Also define the convex hull of a graph with vertex set as the smallest convex set in containing . Then the smallest cardinality of a set whose convex hull is is called the hull number of , denoted .
Let a simple graph have vertices, chromatic polynomial , and chromatic number . Then can be written aswhere and is a falling factorial, and the polynomialis known as the -polynomial (Frucht and Giudici 1983; Li et al. 1987; Read and Wilson 1998, p. 265).-polynomials for a number of simple graphs are summarized in the following table.graph claw graph complete graph 1cubical graphcycle graph octahedral graphpath graph pentatope graph 1square graph star graph star graph tetrahedral graph 1triangle graph 1wheel graph wheel graph
Given a set , let be the set of neighbors of . Then the bipartite graph with bipartitions and has a perfect matching iff for all subsets of .
Let be the number of vertices in a graph and the length of the maximum cycle in . Then the shortness exponent of a class of graphs is defined by
The Hajós number of a graph is the maximum such that contains a subdivision of the complete graph .
Given an undirected graph, a degree sequence is a monotonic nonincreasing sequence of the vertex degrees (valencies) of its graph vertices. The number of degree sequences for a graph of a given order is closely related to graphical partitions. The sum of the elements of a degree sequence of a graph is always even due to fact that each edge connects two vertices and is thus counted twice (Skiena 1990, p. 157).The minimum vertex degree in a graph is denoted , and the maximum vertex degree is denoted (Skiena 1990, p. 157). A graph whose degree sequence contains only multiple copies of a single integer is called a regular graph. A graph corresponding to a given degree sequence can be constructed in the Wolfram Language using RandomGraph[DegreeGraphDistribution[d]].It is possible for two topologically distinct graphs to have the same degree sequence. Moreover, two distinct convex polyhedra can even have the same degree sequence for their..
The shortest path problem seeks to find the shortest path (a.k.a. graph geodesic) connecting two specific vertices of a directed or undirected graph. The length of the graph geodesic between these points is called the graph distance between and . Common algorithms for solving the shortest path problem include the Bellman-Ford algorithm and Dijkstra's algorithm.The Wolfram Language function FindShortestPath[g, u, v] can be used to find one (of possibly mutiple) shortest path between vertices and in a graph .The so-called reaching algorithm can solve the shortest path problem on an -edge graph in steps for an acyclic digraph although it allows edges to be traversed opposite their direction and given a negative length.
A partition is called graphical if there exists a graph having degree sequence . The number of graphical partitions of length is equal to the number of -node graphs that have no isolated points.The numbers of distinct graphical partitions corresponding to graphs on , 2, ... nodes are 0, 1, 2, 7, 20, 71, 240, 871, 3148, ... (OEIS A095268).A graphical partition of order is one for which the sum of degrees is . A -graphical partition only exists for even .It is possible for two topologically distinct graphs to have the same degreesequence, an example of which is illustrated above.The numbers of graphical partitions on , 4, 6, ... edges are 1, 2, 5, 9, 17, 31, 54, 90, 151, 244, ... (OEIS A000569).Erdős and Richmond (1989) showed thatand
Cospectral graphs, also called isospectral graphs, are graphs that share the same graph spectrum. The smallest pair of isospectral graphs is the graph union and star graph , illustrated above, both of which have graph spectrum (Skiena 1990, p. 85). The first example was found by Collatz and Sinogowitz (1957) (Biggs 1993, p. 12). Many examples are given in Cvetkovic et al. (1998, pp. 156-161) and Rücker et al. (2002). The smallest pair of cospectral graphs is the graph union and star graph , illustrated above, both of which have graph spectrum (Skiena 1990, p. 85).The following table summarizes some prominent named cospectral graphs.cospectral graphs126-antiprism graph, quartic vertex-transitive graph Qt1916Hoffman graph, tesseract graph16(4,4)-rook graph, Shrikhande graph2525-Paulus graphs2626-Paulus graphs28Chang graphs, 8-triangular graph70Harries graph, Harries-Wong graphDetermining..
A graphic sequence is a sequence of numbers which can be the degree sequence of some graph. A sequence can be checked to determine if it is graphic using GraphicQ[g] in the Wolfram Language package Combinatorica` .Erdős and Gallai (1960) proved that a degree sequence is graphic iff the sum of vertex degrees is even and the sequence obeys the propertyfor each integer (Skiena 1990, p. 157), and this condition also generalizes to directed graphs. Tripathi and Vijay (2003) showed that this inequality need be checked only for as many as there are distinct terms in the sequence, not for all .Havel (1955) and Hakimi (1962) proved another characterization of graphic sequences, namely that a degree sequence with and is graphical iff the sequence is graphical. In addition, Havel (1955) and Hakimi (1962) showed that if a degree sequence is graphic, then there exists a graph such that the node of highest degree is adjacent to the next highest degree..
Suppose that is a pseudograph, is the edge set of , and is the family of edge sets of graph cycles of . Then obeys the axioms for the circuits of a matroid, and hence is a matroid. Any matroid that can be obtained in this way is a graphic matroid.
Das (2018) defines the triameter of a connected graph with vertex set and vertex count at least 3 aswhere is the graph distance between vertices and .
Let denote the chromatic polynomial of a finite simple graph . Then is said to be chromatically unique if implies that and are isomorphic graphs, in other words, if is determined by its chromatic polynomial. If and are nonisomorphic but share the same chromatic polynomial, they are said to be chromatically equivalent.Cycle graphs are chromatically unique (Chao and Whitehead 1978), as are Turán graphs (Chao and Novacky 1982).Named graphs that are chromatically nonunique include the 3- and 4-barbell graph, bislit cube, bull graph, claw graph, 3-matchstick graph, Moser spindle, 2-Sierpiński sieve graph, star graphs, triakis tetrahedral graph, and 6- and 8-wheel graphs.The numbers of chromatically nonunique simple graphs on nodes for , 2, ... are 0, 0, 0, 4, 18, 115, 905, 11642, 267398, ... (OEIS A137567), while the corresponding numbers of chromatically unique graphs are 1, 2, 4, 7, 16, 41, 139, 704, 7270, ... (OEIS A137568)...
The so-called reaching algorithm can solve the shortest path problem (i.e., the problem of finding the graph geodesic between two given nodes) on an -edge graph in steps for an acyclic digraph. This algorithm allows paths such that edges traversed in the direction opposite their orientation have a negative length.No other algorithm can have better complexity because any other algorithm would have to at least examine every edge, which would itself take steps.
The thickness (or depth) (Skiena 1990, p. 251; Beineke 1997) or (Harary 1994, p. 120) of a graph is the minimum number of planar subgraphs of needed such that the graph union (Skiena 1990, p. 251).The thickness of a planar graph is therefore , and the thickness of a nonplanar graph satisfies .A lower bound for the thickness of a graph is given by(1)where is the number of edges, is the number vertices, and is the ceiling function (Skiena 1990, p. 251). The example above shows a decomposition of the complete graph into three planar subgraphs. This decomposition is minimal, so , in agreement with the bound .The thickness of a complete graph satisfies(2)except for (Vasak 1976, Alekseev and Gonchakov 1976, Beineke 1997). For , 2, ..., the thicknesses are therefore 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, ... (OEIS A124156).The thickness of a complete bipartite graph is given by(3)except possibly when and are both odd, and with there..
Two nonisomorphic graphs are said to be chromatically equivalent if they have identical chromatic polynomials. A graph that does not share a chromatic polynomial with any other nonisomorphic graph is said to be a chromatically unique graph.The chromatically equivalent simple graphs on five or fewer vertices are illustrated above.It appears to be the case that all resistance-equivalentgraphs are also chromatically equivalent.
The projective plane crossing number of a graph is the minimal number of crossings with which the graph can be drawn on the real projective plane.All graphs with crossing number 0 or 1 have projective plane crossing number 0.Richter and Siran (1996) computed the crossing number of the complete bipartite graph on an arbitrary surface. Ho (2005) showed that the projective crossing number of is given byFor , 2, ..., the first few values are therefore 0, 0, 0, 2, 4, 6, 10, 14, 18, 24, ... (OEIS A128422).
The set of graph eigenvalues of the adjacency matrix is called the spectrum of the graph. (But note that in physics, the eigenvalues of the Laplacian matrix of a graph are sometimes known as the graph's spectrum.) The spectrum of a graph with -fold degenerate eigenvalues is commonly denoted (van Dam and Haemers 2003) or (Biggs 1993, p. 8; Buekenhout and Parker 1998).The product over the elements of the spectrum of a graph is known as the characteristic polynomial of , and is given by the characteristic polynomial of the adjacency matrix of with respect to the variable .The largest absolute value of a graph's spectrum is known as its spectralradius.The spectrum of a graph may be computed in the Wolfram Language using Eigenvalues[AdjacencyMatrix[g]]. Precomputed spectra for many named graphs can be obtained using GraphData[graph, "Spectrum"].A graph whose spectrum consists entirely of integers is known as an integralgraph.The..
The skewness of a graph is the minimum number of edges whose removal results in a planar graph (Harary 1994, p. 124). The skewness is sometimes denoted (Cimikowski 1992).A graph with has toroidal crossing number . (However, there exist graphs with that still have .) satisfies(1)where is the vertex count of and its edge count (Cimikowski 1992).The skewness of a disconnected graph is equalto the sum of skewnesses of its connected components.The skewness of a complete graph is given by(2)of the complete bipartite graph by(3)and of the hypercube graph by(4)(Cimikowski 1992).
A canonical labeling, also called a canonical form, of a graph is a graph which is isomorphic to and which represents the whole isomorphism class of (Piperno 2011). The complexity class of canonical labeling is not known.Efficient labeling methods yield an efficient tests for isomorphicgraphs, as provided for example by nauty, Traces, bliss, and other software implementations.
An ordered pair representation is a representation of a directed graph in which edges are specified as ordered pairs or vertex indices. The ordered pairs representation of a directed graph may be computed in the Wolfram Language using List @@@ EdgeList[g], and a graph may be constructed from an ordered pair representation using Graph[DirectedEdge @@@ l].
A bridgeless graph, also called an isthmus-free graph, is a graph that contains no graph bridges. Examples of bridgeless graphs include complete graphs on nodes, cycle graphs, the diamond graph, empty graphs, and the singleton graph.Connected bridgeless graphs are 2-edge connected and can be tested for in the Wolfram Language using KEdgeConnectedGraphQ[g, 2] or EdgeConnectivity[g] .A graph that is not bridgeless is said to be bridged.The numbers of simple bridgeless graphs on , 2, ... vertices are 1, 1, 2, 5, 16, 77, 582, 8002, ... (OEIS A263914).The numbers of simple connected bridgeless graphs on , 2, ... vertices are 1, 0, 1, 3, 11, 60, 502, 7403 ... (OEIS A007146).
A bridged graph is a graph that contains one or more graph bridges. Examples of bridged graphs include path graphs, ladder rung graphs, the bull graph, star graphs, and trees.A graph that is not bridged is said to be bridgeless. A connected bridgeless graph can be tested for in the Wolfram Language using Not[KEdgeConnectedGraphQ[g, 2]] or EdgeConnectivity[g] .The numbers of simple bridged graphs on , 2, ... vertices are 0, 1, 2, 6, 18, 79, 462, 4344, ... (OEIS A263915).The numbers of simple connected bridged graphs on , 2, ... vertices are 0, 1, 1, 3, 10, 52, 351, 3714, 63638, 1912203, ... (OEIS A052446).
The graph neighborhood of a vertex in a graph is the set of all the vertices adjacent to including itself. More generally, the th neighborhood of is the set of all vertices that lie at the distance from .The subgraph induced by the neighborhood of a graph from vertex is called the neighborhood graph.Note that while "graph neighborhood" generally includes vertices adjacent to together with the vertex itself, the term "graph neighbors" generally means vertices adjacent to excluding itself (e.g., Brouwer et al. 1989), so some care is needed when encountering these terms.
A block is a maximal biconnected subgraph of a given graph . In the illustration above, the blocks are , , and .If a graph is biconnected, then itself is called a block (Harary 1994, p. 26) or a biconnected graph (Skiena 1990, p. 175).
A shortest path between two graph vertices of a graph (Skiena 1990, p. 225). There may be more than one different shortest paths, all of the same length. Graph geodesics may be found using a breadth-first traversal (Moore 1959) or using Dijkstra's algorithm (Skiena 1990, p. 225). One (of possibly several) graph geodesics of a graph from vertex to vertex can be found in the Wolfram Language using FindShortestPath[g, u, v]. The length of the graph geodesic between these points is called the graph distance between and .The length of the maximum geodesic in a given graph is called the graph diameter, and the length of the minimum geodesic is called the graph radius.The matrix consisting of all graph distances from vertex to vertex is known as the all-pairs shortest path matrix, or more simply, the graph distance matrix...
The genus of a graph is the minimum number of handles that must be added to the plane to embed the graph without any crossings. Special cases are summarized in the following table (West 2000, p. 266).class0planar graph1toroidal graph2double-toroidal graph3pretzel graphThere are no pretzel graphs on eight or fewer vertices.Duke and Haggard (1972; Harary et al. 1973) gave a criterion for the genus of all graphs on 8 and fewer vertices. Define the double-toroidal graphs(1)(2)(3)where denotes minus the edges of . Then for any subgraph of : 1. if does not contain a Kuratowski graph (i.e., or ), 2. if contains a Kuratowski graph (i.e., is nonplanar) but does not contain any for , 3. if contains any for . The complete graph has genus(4)for , where is the ceiling function (Ringel and Youngs 1968; Harary 1994, p. 118). The values for , 2, ... are 0, 0, 0, 0, 1, 1, 1, 2, 3, 4, 5, 6, 8, 10, ... (OEIS A000933).The complete bipartite graph has genus(5)(Ringel..
The eigenvalues of a graph are defined as the eigenvalues of its adjacency matrix. The set of eigenvalues of a graph is called a graph spectrum.The largest eigenvalue absolute value in a graph is called the spectral radius of the graph, and the second smallest eigenvalue of the Laplacian matrix of a graph is called its algebraic connectivity.
An articulation vertex of a connected graph is a vertex whose removal will disconnect the graph (Chartrand 1985). More generally, an articulation vertex is a vertex of a not-necessarily-connected graph whose removal increases the connected component count (Harary 1994, p. 26). Articulation vertices are also called cut-vertices or "cutpoints" (Harary 1994, p. 26).A graph on two or more vertices possessing no articulation vertices is called a biconnected graph. A vertex is an articulation vertex iff it appears in two biconnected components.The endpoints of a graph bridge are articulation vertices unless they both have vertex degree 1. On the other hand, it is possible for a non-bridge edge to have both endpoints be articulation vertices.The Wolfram Language function FindVertexCut[g] returns a vertex cut set of smallest size for a graph, which corresponds to an articulation vertex if the set is of size 1.The analog..
A minimum vertex cover is a vertex cover having the smallest possible number of vertices for a given graph. The size of a minimum vertex cover of a graph is known as the vertex cover number and is denoted .Every minimum vertex cover is a minimal vertex cover (i.e., a vertex cover that is not a proper subset of any other cover), but not necessarily vice versa.Finding a minimum vertex cover of a general graph is an NP-complete problem. However, for a bipartite graph, the König-Egeváry theorem allows a minimum vertex cover to be found in polynomial time.A minimum vertex cover of a graph can be computed in the Wolfram Language using FindVertexCover[g]. There is currently no Wolfram Language function to compute all minimum vertex covers.Minimum vertex covers correspond to the complements of maximumindependent vertex sets. ..
A minimum edge cover is an edge cover having the smallest possible number of edges for a given graph. The size of a minimum edge cover of a graph is known as the edge cover number of and is denoted .Every minimum edge cover is a minimal edge cover (i.e., not a proper subset of any other edge cover), but not necessarily vice versa.Only graphs with no isolated points have an edge cover (and therefore a minimum edge cover).A minimum edge cover of a graph can be computed in the Wolfram Language with FindEdgeCover[g]. There is currently no Wolfram Language function to compute all minimum edge covers of a graph.If a graph has no isolated points, thenwhere is the matching number and is the vertex count of (Gallai 1959, West 2000).
The distance between two vertices and of a finite graph is the minimum length of the paths connecting them (i.e., the length of a graph geodesic). If no such path exists (i.e., if the vertices lie in different connected components), then the distance is set equal to . In a grid graph the distance between two vertices is the sum of the "vertical" and the "horizontal" distances (right figure above).The matrix consisting of all distances from vertex to vertex is known as the all-pairs shortest path matrix, or more simply, the graph distance matrix.
The coarseness of a graph is the maximum number of edge-disjoint nonplanar subgraphs contained in a given graph . The coarseness of a planar graph is therefore .Harary (1994, pp. 121-122) gives formulas for the coarseness of and .
The circumference of a graph is the length of any longest cycle in a graph. Hamiltonian graphs on vertices therefore have circumference of .For a cyclic graph, the maximum element of the detour matrix over all adjacent vertices is one smaller than the circumference.The graph circumference of a self-complementary graph is either (i.e., the graph is Hamiltonian), , or (Furrigia 1999, p. 51).Circumferences of graphs for various classes of nonhamiltonian graphs are summarized in the table below.classcircumferenceerefbarbell graph-bishop graphbook graph 6complete bipartite graph for -cone graphgear graphgrid graph grid graph helm graph-knight graphpan graphsunlet graph web graphwheel graph -windmill graph
The matching number of graph , sometimes known as the edge independence number, is the size of a maximum independent edge set. Equivalently, it is the degree of the matching-generating polynomial(1)where is the number of -matchings of a graph . The notations , , or are sometimes also used. satisfies(2)where is the vertex count of , is the floor function. Equality occurs only for a perfect matching, and graph has a perfect matching iff(3)where is the vertex count of .The matching number of a graph is equal to the independence number of its line graph .The König-Egeváry theorem states that the matching number equals the vertex cover number (i.e., size of the smallest minimum vertex cover) are equal for a bipartite graph.If a graph has no isolated points, then(4)where is the matching number, is the size of a minimum edge cover, and is the vertex count of (West 2000).Precomputed matching numbers for many named graphs are available in the..
The bandwidth of a graph is the minimum matrix bandwidth among all possible adjacency matrices of graphs isomorphic to . Equivalently, it is the minimum graph dilation of a numbering of a graph. Bandwidth is variously denoted , , or .The bandwidth of the singleton graph is not defined, but the conventions or (Miller 1988) are sometimes adopted.The bandwidth of a disconnected graph is themaximum of the bandwidths of its connected components.The bandwidth of a connected graph satisfies the inequalities(Chinn et al. 1982), where is the vertex count of and is the graph diameter andwhere is the chromatic number.Computing the bandwidth of a graph is NP-hard.Bounds for the bandwidth of a graph have been considered by (Harper 1964), and the bandwidth of the -cube was determined by Harper (Harper 1966, Wang and Wu 2007, Harper 2010).Special cases are summarized in the following table.graphbandwidthantiprism graph4cocktail party graph complete..
Let be the number of edge covers of a graph of size . Then the edge cover polynomial is defined by(1)where is the edge count of (Akban and Oboudi 2013).Cycle graphs and complete bipartite graphs are determined by their edge cover polynomials (Akban and Oboudi 2013).The edge cover polynomial is multiplicative over graph components, so for a graph having connected components , , ..., the edge cover polynomial of itself is given by(2)The edge cover polynomial satisfies(3)where is the vertex count of a graph and is its independence polynomial (Akban and Oboudi 2013).The following table summarizes sums for the edge cover polynomials of some common classes of graphs (Akban and Oboudi 2013).graphcomplete bipartite graph complete graph cycle graph path graph The following table summarizes closed forms for the edge cover polynomials of some common classes of graphs.graphbook graph cycle graph helm graphpath graph star graph sunlet graph The following..
The size of a minimum edge cover in a graph is known as the edge cover number of , denoted .If a graph has no isolated points, thenwhere is the matching number and is the vertex count of (Gallai 1959, West 2000).
An edge cover is a subset of edges defined similarly to the vertex cover (Skiena 1990, p. 219), namely a collection of graph edges such that the union of edge endpoints corresponds to the entire vertex set of the graph. Therefore, only graphs with no isolated points have an edge cover.A graph can be tested in the Wolfram Language to see if it is an edge cover of a given graph using EdgeCoverQ[g]. Precomputed edge covers for many named graphs can be looked up using GraphData[graph, "EdgeCovers"].An edge cover having the smallest possible number of edges for a given graph is known as a minimum edge cover. A minimum edge cover of a graph can be found in the Wolfram Language using FindEdgeCover[g]. An edge cover that does not contain any other edge cover as a proper subset is known as a minimal edge cover...
The triangular snake graph is the graph on vertices with odd defined by starting with the path graph and adding edges for , ..., . The first few are illustrated above, and special cases are summarized in the following table.1singleton graph 3triangle graph 5butterfly graphTriangular snakes are unit-distance and matchstick by construction, perfect. They are graceful when the number of triangles is congruent to 0 or 1 (mod 4) (Moulton 1989, Gallian 2018), which is equivalent to when .
A kayak paddle graph is the graph obtained by joining cycle graphs and by a path of length (Gallian 2018). is isomorphic to the 3-barbell graph.Kayak paddle graphs are planar, cactus, unit-distance and matchstick graphs. They are also bridged and traceable and have arboricity of 2.Litersky (2011) proved that kayak paddle graphs are gracefulwhen: 1. , , 2. (mod 4) for , 3. , (Litersky 2011, Gallian 2018).
The graph categorical product, also called the tensor product, is the graph product denoted and defined by the adjacency relations ( and ).The graph categorical product is known as the bipartite double graph of .
"The" Y-graph is another term used to refer to a clawgraph.The term "Y-graph" is also used to refer to a graph expansion with the Y graph as its base (e.g., Horton and Bouwer 1991). There are exactly four graph expansions with Y-graph base that are symmetric (Biggs 1993, p. 147).graphexpansion 28Coxeter graph(7; 1, 2, 4)56cubic symmetric graph (14; 1, 3, 5)112cubic symmetric graph (28; 1, 3, 9)224cubic symmetric graph (56; 1, 9, 25)
In general, a graph product of two graphs and is a new graph whose vertex set is and where, for any two vertices and in the product, the adjacency of those two vertices is determined entirely by the adjacency (or equality, or non-adjacency) of and , and that of and . There are cases to be decided (three possibilities for each, with the case where both are equal eliminated) and thus there are different types of graph products that can be defined.The most commonly used graph products, given by conditions sufficient and necessary for adjacency, are summarized in the following table (Hartnell and Rall 1998). Note that the terminology is not quite standardized, so these products may actually be referred to by different names by different sources (for example, the graph lexicographic product is also known as the graph composition; Harary 1994, p. 21). Many other graph products can be found in Jensen and Toft (1994).Graph products can be computed using..
The Cartesian graph product , sometimes simply called "the" graph product (Beineke and Wilson 2004, p. 104) and sometimes denoted (e.g., Salazar and Ugalde 2004) of graphs and with disjoint point sets and and edge sets and is the graph with point set and adjacent with whenever or (Harary 1994, p. 22).Graph Cartesian products can be computed using the undocumented Wolfram Language function GraphComputation`GraphProduct[G1, G2, "Cartesian"].The following table gives examples of some graph Cartesian products. Here, denotes a cycle graph, a complete graph, a path graph, and a star graph.productresultgrid graph ladder graph grid graph prism graph stacked prism graph torus grid graph with circulant graph book graphstacked book graphcrown graph rook graph rook complement graphhypercube graph ..
The contraction of a pair of vertices and of a graph produces a graph in which the two nodes and are replaced with a single node such that is adjacent to the union of the nodes to which and were originally adjacent. In vertex contraction, it doesn't matter if and are connected by an edge; if they are, the edge is simply removed upon contraction (Pemmaraju and Skiena 2003, p. 231). Note that Skiena (1990, p. 91) is ambiguous about the distinction between vertex contraction and edge contraction, and confusingly refers to vertex contraction on vertices and as "contracting an edge ."The figure above shows a random graph contracted on vertices and . Vertex contraction can be implemented using Contract[g, v1, v2] in the Wolfram Language package Combinatorica` .
The th power of a graph is a graph with the same set of vertices as and an edge between two vertices iff there is a path of length at most between them (Skiena 1990, p. 229). Since a path of length two between vertices and exists for every vertex such that and are edges in , the square of the adjacency matrix of counts the number of such paths. Similarly, the th element of the th power of the adjacency matrix of gives the number of paths of length between vertices and . Graph powers are implemented in the Wolfram Language as GraphPower[g, k].The graph th power is then defined as the graph whose adjacency matrix given by the sum of the first powers of the adjacency matrix,which counts all paths of length up to (Skiena 1990, p. 230).Raising any graph to the power of its graph diameter gives a complete graph. The square of any biconnected graph is Hamiltonian (Fleischner 1974, Skiena 1990, p. 231). Mukhopadhyay (1967) has considered "square..
An automorphism of a graph is a graph isomorphism with itself, i.e., a mapping from the vertices of the given graph back to vertices of such that the resulting graph is isomorphic with . The set of automorphisms defines a permutation group known as the graph's automorphism group. For every group , there exists a graph whose automorphism group is isomorphic to (Frucht 1939; Skiena 1990, p. 185). The automorphism groups of a graph characterize its symmetries, and are therefore very useful in determining certain of its properties.The group of graph automorphisms of a graph may be computed in the Wolfram Language using GraphAutomorphismGroup[g], the elements of which may then be extracted using GroupElements. A number of software implementations exist for computing graph automorphisms, including nauty by Brendan McKay and SAUCY2, the latter of which performs several orders of magnitude faster than other implementations based on empirical..
A topological sort is a permutation of the vertices of a graph such that an edge implies that appears before in (Skiena 1990, p. 208). Only acyclic digraphs can be topologically sorted. The topological sort of a graph can be computed using TopologicalSort[g] in the Wolfram Language package Combinatorica` .
Given a planar graph , its geometric dual is constructed by placing a vertex in each region of (including the exterior region) and, if two regions have an edge in common, joining the corresponding vertices by an edge crossing only . The result is always a planar pseudograph. However, an abstract graph with more than one embedding on the sphere can give rise to more than one dual.Whitney showed that the geometric dual graph and combinatorial dual graph are equivalent (Harary 1994, p. 115), and so may simply be called "the" dual graph.
A graph is a minor of a graph if a copy of can be obtained from via repeated edge deletion and/or edge contraction.The Kuratowski reduction theorem states that any nonplanar graph has the complete graph or the complete bipartite graph as a minor. In addition, any snark has the Petersen graph as a minor, as conjectured by Tutte (1967; West 2000, p. 304) and proved by Robertson et al. The determination of graph minors is an NP-hard problem for which no good algorithms are known, although brute-force methods such as those due to Robertson, Sanders, and Thomas exist.
The graph product denoted and defined by the adjacency relations () or ( and ). The graph lexicographic product is also known as the graph composition (Harary 1994, p. 21).The "double graph" of a given graph is the graph lexicographic product .
Let be a (not necessarily simple) undirected edge-weighted graph with nonnegative weights. A cut of is any nontrivial subset of , and the weight of the cut is the sum of weights of edges crossing the cut. A mincut is then defined as a cut of of minimum weight. The problem is polynomial time solvable as a series of network flow problems or using the algorithm of Stoer and Wagner (1994).
The join of graphs and with disjoint point sets and and edge sets and is the graph union together with all the edges joining and (Harary 1994, p. 21). Graph joins can be computed using GraphJoin[G1, G2] in the Wolfram Language package Combinatorica` .A complete -partite graph is the graph join of empty graphs on , , ... nodes. A wheel graph is the join of a cycle graph and the singleton graph. Finally, a star graph is the join of an empty graph and the singleton graph (Skiena 1990, p. 132).The following table gives examples of some graph joins. Here denotes an empty graph (i.e., the graph complement of the complete graph ), a cycle graph, and the singleton graph.productresultcomplete -partite graph wheel graph star graph cone graph fan graph
Let be a (not necessarily simple) undirected edge-weighted graph with nonnegative weights. A cut of is any nontrivial subset of , and the weight of the cut is the sum of weights of edges crossing the cut. A maxcut is then defined as a cut of of maximum weight. Determining the maxcut of a graph is an NP-hard problem.
In a graph , contraction of an edge with endpoints is the replacement of and with a single vertex such that edges incident to the new vertex are the edges other than that were incident with or . The resulting graph has one less edge than .Graph minors are defined in terms of edge contractions.
Let be the vertex set of a simple graph and its edge set. Then a graph isomorphism from a simple graph to a simple graph is a bijection such that iff (West 2000, p. 7).If there is a graph isomorphism for to , then is said to be isomorphic to , written .There exists no known P algorithm for graph isomorphism testing, although the problem has also not been shown to be NP-complete. As a result, the special complexity class graph isomorphism complete is sometimes used to refer to the problem of graph isomorphism testing.
The set of all edge automorphisms of , denoted . Let be the line graph of a graph . Then the edge automorphism group is isomorphic to ,(Holton and Sheehan 1993, p. 26).
Let be a set and a nonempty family of distinct nonempty subsets of whose union is . The intersection graph of is denoted and defined by , with and adjacent whenever and . Then a graph is an intersection graph on if there exists a family of subsets for which and are isomorphic graphs (Harary 1994, p. 19). Graph intersections can be computed in the Wolfram Language using GraphIntersection[g, h].
An edge automorphism of a graph is a permutation of the edges of that sends edges with common endpoint into edges with a common endpoint. The set of all edge automorphisms of from a group called the edge automorphism group of , denoted .
"The" graph is the path graph on two vertices: .An -graph for and is a generalization of a generalized Petersen graph and has vertex setand edge setwhere the subscripts are read modulo (Bouwer et al. 1988, itnik et al. ). Such graphs can be constructed by graph expansion on .If the restriction is relaxed to allow and to equal , gives the ladder rung graph and gives the sunlet graph .Two -graphs and are isomorphic iff there exists an integer relatively prime to such that either or (Boben et al. 2005, Horvat et al. 2012, itnik 2012).The graph is connected iff . If , then the graph consists of copies of (itnik et al. 2012).The -graph corresponds to copies of the graph The following table summarizes special named -graphs and classes of named -graphs.graphcubical graph Petersen graph Dürer graphMöbius-Kantor graphdodecahedral graphDesargues graphNauru graphprism graph generalized Petersen graph All -graphs..
Given any tree having vertices of vertex degrees of 1 and 3 only, form an -expansion by taking disjoint copies of and joining corresponding leaves by an -cycle where, however, the th leaf on the th copy need not be connected to the th leaf on the st copy, but will in general be connected to the th copy. The set of values are known as the steps.The resulting graphs are always cubic, and there exist exactly 13 graph expansions that are symmetric as well, as summarized in the following table (Biggs 1993, p. 147). E. Gerbracht (pers. comm., Jan. 29, 2010) has shown that all the graphs in this table are unit-distance.graphFostergeneralized Petersen graphbase graphexpansion 8cubical graph I graph(4; 1, 1)10Petersen graphI graph(5; 1, 2)16Möbius-Kantor graphI graph(8; 1, 3)20dodecahedral graphI graph(10; 1, 2)20Desargues graphI graph(10; 1, 3)24Nauru graphI graph(12; 1, 5)28Coxeter graphY graph(7; 1, 2, 4)48cubic symmetric..
A tree is a mathematical structure that can be viewed as either a graph or as a data structure. The two views are equivalent, since a tree data structure contains not only a set of elements, but also connections between elements, giving a tree graph.Trees were first studied by Cayley (1857). McKay maintains a database of trees up to 18 vertices, and Royle maintains one up to 20 vertices.A tree is a set of straight line segments connected at their ends containing no closed loops (cycles). In other words, it is a simple, undirected, connected, acyclic graph (or, equivalently, a connected forest). A tree with nodes has graph edges. Conversely, a connected graph with nodes and edges is a tree. All trees are bipartite graphs (Skiena 1990, p. 213). Trees with no particular node singled out are sometimes called free trees (or unrooted tree), by way of distinguishing them from rooted trees (Skiena 1990, Knuth 1997).The points of connection are known..
A generalized Moore graph is a regular graph of degree where the counts of vertices at each distance , 1, ... from any vertex are 1, , , , , ..., with the last distance count not necessarily filled up. That is, all the levels are full except possibly the last which must have the rest. Alternatively, the girth is as great as the naive bound allows and the diameter is as little as the naive bound allows. Stated yet another way, a generalized Moore graph is a regular graph such that the average distance between pairs of vertices achieves the naive lower bound.The numbers of generalized Moore graphs with , 2, ... nodes are 0, 0, 0, 1, 1, 4, 3, 13, 21, ... (OEIS A088933).The numbers of cubic generalized Moore graphs with , 4, 6, ... nodes are 0, 1, 2, 2, 1, 2, 7, 6, 1, 1, ... (OEIS A005007).It is an open problem if there are infinitely many generalized Moore graphs of each degree...
Percolation theory deals with fluid flow (or any other similar process) in random media.If the medium is a set of regular lattice points, then there are two main types of percolation: A site percolation considers the lattice vertices as the relevant entities; a bond percolation considers the lattice edges as the relevant entities. These two models are examples of discrete percolation theory, an umbrella term used to describe any percolation model which takes place on a regular point lattice or any other discrete set, and while they're most certainly the most-studied of the discrete models, others such as AB percolation and mixed percolation do exist and are reasonably well-studied in their own right.Contrarily, one may also talk about continuum percolation models, i.e.,models which attempt to define analogous tools and results with respect to continuous, uncountable domains. In particular, continuum percolation theory involves notions..
Percolation, the fundamental notion at the heart of percolation theory, is a difficult idea to define precisely though it is quite easy to describe qualitatively.From the narrowest perspective, the term percolation can be defined as a model of a porous medium; indeed, it is from this perspective that the study of percolation theory blossomed, and is typically agreed to be the fundamental physical situation that modern percolation theory attempts to address.Likewise, it is not uncommon for the term percolation to describe the actual fluid flow within the random media or as the theoretical simulation of such a flow for a given simulated medium.One of the difficulties underlying the formulation of a precise definition is that some authors choose to define the term relative to the machinery used in its study. For instance, some authors choose to define percolation to be the result of independently removing vertices or edges from some sort of graph..
The disk model is the standard Boolean-Poisson model in two-dimensional continuum percolation theory. In particular, the disk model is characterized by the existence of a Poisson process in which distributes the centers of a collection of closed disks (i.e., two-dimensional closed balls) along with a random process which independently assigns random radii to each .The disks which make up the disk model are known as randomdisks.
An percolation is a discrete percolation model in which the underlying point lattice graph has the properties that each of its graph vertices is occupied by an atom either of type or of type , that there is a probability that any given vertex is occupied by an atom of type , and that different vertices are occupied independently of each other.In this model, a graph edge of is said to be open if its end vertices are occupied by atoms of different types and is said to be closed otherwise. The idea is based on the hypothesis that dissimilar atoms bond together whereas similar atoms repel one another.This model is sometimes studied under the title antipercolation.
Zarankiewicz's conjecture asserts that graph crossing number for a complete bipartite graph is(1)where is the floor function. The original proof by Zarankiewicz (1954) contained an error, but was subsequently solved in some special cases by Guy (1969). Zarankiewicz (1954) showed that in general, the formula provides an upper bound to the actual number.The problem addressed by the conjecture is sometimes known as the brick factory problem, since it was described by Turán (1977) as follows: "We worked near Budapest, in a brick factory. There were some kilns where the bricks were made and some open storage yards where the bricks were stored. All the kilns were connected to all the storage yards. The bricks were carried on small wheeled trucks to the storage yards. All we had to do was to put the bricks on the trucks at the kilns, push the trucks to the storage yards, and unload them there. We had a reasonable piece rate for the trucks, and..
The torus grid graph is the graph formed from the graph Cartesian product of the cycle graphs and . is isomorphic to . can be formed starting with an grid graph and connecting corresponding left/right and top/bottom vertex pairs with edges. While such an embedding has overlapping edges in the plane, it can naturally be placed on the surface of a torus with no edge intersections or overlaps. Torus grid graphs are therefore toroidal graphs. The isomorphic torus grid graphs and are illustrated above.The torus grid graphs are quartic and Hamiltonianand have vertex count(1)Torus grid graphs are circulant graphs iff and are relatively prime, i.e., . In such cases, is isomorphic to . Special cases are summarized in the following table and illustrated above in attractive (but non-toroidal) embddings.graphcirculant graph generalized quadrangle quartic vertex-transitive graph Qt65tesseract graph Harary et al. (1973) conjectured that(2)for all..
The smallest cubic graphs with graph crossing number have been termed "crossing number graphs" or -crossing graphs by Pegg and Exoo (2009). The -crossing graphs are implemented in the Wolfram Language as GraphData["CrossingNumberGraphNA"], with N being a number and X a letter, for example 3C for the Heawood graph or 8B for cubic symmetric graph .The following table summarizes and updates the smallest cubic graphs having given crossing number, correcting Pegg and Exoo (2009) by and by omitting two of the three unnamed 24-node graphs (CNG 8D and CNG 8E) given as having crossing number 8 (but which actually have crossing number 7), noting that the 26-node graph here called CNG 9A and labeled as "McGee + edge" (corresponding to one of two certain edge insertions in the McGee graph) actually has (not 10), and adding the edge-excised Coxeter graph as CNG 9 B. In addition, the 28-node graphs CNG 10A with crossing number..
Guy's conjecture, which has not yet been proven or disproven, states that the graph crossing number for a complete graph is(1)where is the floor function, which can be rewritten(2)The values for , 2, ... are then given by 0, 0, 0, 0, 1, 3, 9, 18, 36, 60, 100, 150, 225, 315, 441, 588, ... (OEIS A000241).Guy (1972) proved the conjecture for , a result extended to by Pan and Richter (2007).It is known that(3)(Richter and Thomassen 1997, de Klerk et al. 2007, Pan and Richter 2007).
Given a "good" graph (i.e., one for which all intersecting graph edges intersect in a single point and arise from four distinct graph vertices), the crossing number is the minimum possible number of crossings with which the graph can be drawn, including using curved (non-rectilinear) edges. Several notational conventions exist in the literature, with some of the more common being (e.g., Pan and Richter 2007; Clancy et al. 2019), , (e.g., Pach and Tóth 2005), and .A graph with crossing number 0 is a planar graph. However, there appears to be no term in standard use for a graph with graph crossing number 1 (the terms "almost planar" and "1-planar" are used in the literature for other concepts). Checking if a graph has crossing number 1 is straightforward using the following algorithm (M. Haythorpe, pers. comm., Apr. 16, 2019). First, confirm that the graph is nonplanar. Then, for all non-adjacent..
For a permutation in the symmetric group , the -permutation graph of a labeled graph is the graph union of two disjoint copies of (say, and ), together with the lines joining point of with of (Harary 1994, p. 175).Skiena (1990, p. 28) defines a permutation graph as a graph whose edges correspond exactly to being a permutation inversion is some permutation , i.e., but occurs before in . The above graph corresponds to the permutation , which has permutation inversion . Permutation graphs are implemented as PermutationGraph[p] in the Wolfram Language package Combinatorica` .
A transposition graph is a graph whose nodes correspond to permutations and edges to permutations that differ by exactly one transposition (Skiena 1990, p. 9, Clark 2005).The transposition graph has vertex count , edge count (for ), and is regular of degree (Clark 2005). All cycles in transposition graphs are of even length, making them bipartite.The transposition graph of a multiset is always Hamiltonian(Chase 1973).Special cases are summarized in the table below.1singleton graph 22-path graph 3utility graph 4Reye graph
"The" butterfly graph is a name sometimes given to the 5-vertex graph illustrated above. This graph is also known as the "bowtie graph" (West 2000, p. 12) and is the triangular snake graph . The butterfly graph is ungraceful (Horton 2003). It is implemented in the Wolfram Language as GraphData["ButterflyGraph"].A different type of butterfly graph is defined as follows. The -dimensional butterfly graph is a directed graph whose vertices are pairs , where is a binary string of length and is an integer in the range 0 to and with directed edges from vertex to iff is identical to in all bits with the possible exception of the th bit counted from the left.The -dimensional butterfly graph has vertices and edges, and can be generated in the Wolfram Language using ButterflyGraph[n, b] (with )...
The -hypercube graph, also called the -cube graph and commonly denoted or , is the graph whose vertices are the symbols , ..., where or 1 and two vertices are adjacent iff the symbols differ in exactly one coordinate.The graph of the -hypercube is given by the graph Cartesian product of path graphs . The -hypercube graph is also isomorphic to the Hasse diagram for the Boolean algebra on elements.The above figures show orthographic projections of some small -hypercube graphs using the first two of each vertex's set of coordinates. Note that above is a projection of the usual cube looking along a space diagonal so that the top and bottom vertices coincide, and hence only seven of the cube's eight vertices are visible. In addition, three of the central edges connect to the upper vertex, while the other three connect to the lower vertex.Hypercube graphs may be computed in the Wolfram Language using the command HypercubeGraph[n], and precomputed properties..
A graph is planar if it can be drawn in a plane without graph edges crossing (i.e., it has graph crossing number 0). The number of planar graphs with , 2, ... nodes are 1, 2, 4, 11, 33, 142, 822, 6966, 79853, ... (OEIS A005470; Wilson 1975, p. 162), the first few of which are illustrated above.The corresponding numbers of planar connected graphs are 1, 1, 1, 2, 6, 20, 99, 646, 5974, 71885, ... (OEIS A003094; Steinbach 1990, p. 131)There appears to be no term in standard use for a graph with graph crossing number 1 (the terms "almost planar" and "1-planar" are used in the literature for other concepts).Note that while graph planarity is an inherent property of a graph, it is still sometimes possible to draw nonplanar embeddings of planar graphs. For example, the two embeddings above both correspond to the planar tetrahedral graph, but while the left embedding is planar, the right embedding is not.A planar embedding of a..
The voter model is a simple mathematical model of opinion formation in which voters are located at the nodes of a network, each voter has an opinion (in the simplest case, 0 or 1, but in the general case, ), and a randomly chosen voter assumes the opinion of one of its neighbors.This model can be used to describe the phase transition behavior of idealized physical systems and can result in a rather remarkable amount of structure starting from a given "random" input." It can be modeled very easily using cellular automata.It turns out that in finite networks (i.e., any real model), fluctuations always cause the system to reach an "absorbing" (i.e., constant) state.
The Desargues graph is the cubic symmetric graph on 20 vertices and 30 edges illustrated above in several embeddings. It is isomorphic to the generalized Petersen graph and to the bipartite Kneser graph . It is the incidence graph of the Desargues configuration. It can be represented in LCF notation as (Frucht 1976). It can also be constructed as the graph expansion of with steps 1 and 3, where is a path graph. It is distance-transitive and distance-regular graph and has intersection array .The Desargues graph is one of three cubic graphs on 20 nodes with smallest possible graph crossing number of 6 (the others being two unnamed graphs denoted CNG 6B and CNG 6C by Pegg and Exoo 2009), making it a smallest cubic crossing number graph (Pegg and Exoo 2009, Clancy et al. 2019).The Desargues is an integral graph with graph spectrum . It is cospectral with another nonisomorphic graph (Haemers and Spence 1995, van Dam and Haemers 2003).It is also a unit-distance..
The Shrikhande graph is a strongly regular graph on 16 nodes. It is cospectral with the rook graph , so neither of the two is determined by spectrum.The Shrikhande graph is the smallest distance-regular graph that is not distance-transitive (Brouwer et al. 1989, p. 136). It has intersection array .The Shrikhande graph is implemented in the WolframLanguage as GraphData["ShrikhandeGraph"].The Shrikhande graph has two generalized LCF notations of order 8, eleven of order 4, 53 of order 2, and 2900 of order 1. The graphs with LCF notations of orders four and eight are illustrated above.The Shrikhande graph appears on the cover of the book Combinatorial Matrix Theoryby Brualdi and Ryser (1991); illustrated above.The plots above show the adjacency, incidence, and graph distance matrices for the Shrikhande graph.It is an integral graph with graph spectrum .The bipartite double graph of the Shrikhandegraph is the Kummer graph.The..
The cocktail party graph of order , also called the hyperoctahedral graph (Biggs 1993, p. 17) or Roberts graph, is the graph consisting of two rows of paired nodes in which all nodes but the paired ones are connected with a graph edge. It is the graph complement of the ladder rung graph , and the dual graph of the hypercube graph . It is the skeleton of the -cross polytope.This graph arises in the handshake problem. It is a complete n-partite graph that is denoted by Brouwer et al. (1989, pp. 222-223), and is distance-transitive, and hence also distance-regular.The cocktail party graph of order is isomorphic to the circulant graph . The -cocktail party graph is also the -Turán graph.Special cases are summarized in the following table.-cocktail party graph1empty graph 2square graph 3octahedral graph416-cell graphThe -cocktail party graph has independence polynomialwith corresponding recurrence equation..
The flower snarks are a family of snarks discovered by Isaacs (1975) and denoted . is Tietze's graph, which is a "reducible snark" since it contains a cycle of length less than 5. is illustrated above in two embeddings, the second of which appears in Scheinerman and Ullman (2011, p. 96) as an example of a graph with edge chromatic number and fractional edge chromatic number (4 and 3, respectively) both integers but not equal. is maximally nonhamiltonian for odd (Clark and Entringer 1983).
A cactus graph, sometimes also called a cactus tree, a mixed Husimi tree, or a polygonal cactus with bridges, is a connected graph in which any two graph cycles have no edge in common. Equivalently, it is a connected graph in which any two (simple) cycles have at most one vertex in common.The inequalitywhere is the circuit rank and is the total number of undirected graph cycles holds for a connected graph iff it is a cactus graph (Volkmann 1996).Every cycle of a cactus graph is therefore chordless. However, there exist graphs (e.g., the -graph and Pasch graph) whose cycles are all chordless but which are not cactus graphs.Every cactus graph is a unit-distance graph(Erdős et al. 1965).Every pseudotree is a cactus graph.The numbers of cactus graphs on 1, 2, ... nodes are 1, 1, 2, 4, 9, 23, 63, 188, ...(OEIS A000083)...
The -centipede graph, -centipede tree, or simply "-centipede," is the tree on nodes obtained by joining the bottoms of copies of the path graph laid in a row with edges. It is therefore isomorphic to the -firecracker graph, with special cases summarized in the table below.graph1path graph 2path graph 3E graphThe rank polynomial of the centipede is given by
A spider graph, spider tree, or simply "spider," is a tree with one vertex of degree at least 3 and all others with degree at most 2. The numbers of spiders on , 2, ... nodes are 0, 0, 0, 1, 2, 4, 7, 11, 17, 25, 36, 50, 70, 94, ... (OEIS A004250).The count of spider trees with nodes is the same as the number of integer partitions of into three or more parts. It also has closed form(1)where is the partition function P and is the floor function. A generating function for is given by(2)(3)(4)where is a q-Pochhammer symbol.Not all spiders are caterpillar graphs, norare all spiders lobster graphs.
Tutte (1971) conjectured that all 3-connected bicubic graphs are Hamiltonian (the Tutte conjecture). The Horton graph on 96 nodes, illustrated above, provided the first counterexample (Bondy and Murty 1976, p. 240).Horton (1982) subsequently found a counterexample on 92 nodes, and two smaller (nonisomorphic) counterexamples on 78 nodes were found by Ellingham (1981, 1982b) and Owens (1983). Ellingham and Horton (1983) subsequently found a counterexample graph on 54 nodes and 81 edges. The smallest currently known counterexample is the 50-node Georges graph (Georges 1989; Grünbaum 2006, 2009).These small known counterexamples are summarized in the following table and illustrated above.namereference50Georges graphGeorges (1989), Grünbaum (2006, 2009)54Ellingham-Horton 54-graphEllingham and Horton (1983)78Ellingham-Horton 78-graphEllingham (1981, 1982)78Owens graphOwens (1983)92Horton 92-graphHorton..
The Meredith graph is a quartic graph on 70 nodes and 140 edges that is a counterexample to the conjecture that every 4-regular 4-connected graph is Hamiltonian.It is implemented in the Wolfram Languageas GraphData["MeredithGraph"].The Meredith graph has chromatic number 3 andedge chromatic number 5.The plots above show the adjacency, incidence,and distance matrices of the graph.
Cubic nonhamiltonian graphs are nonhamiltonian graphs that are also cubic. The numbers of connected cubic nonhamiltonian graphs on , 12, ... are 2, 5, 35, 219, 1666, ... (OEIS A164919). The figure above shows some nonhamiltonian connected cubic graphs that are not snarks.Cubic nonhamiltonian graphs are of special interest because of Tait's Hamiltonian graph conjecture. The cubic polyhedral nonhamiltonian graphs illustrated above all provide counterexamples to this conjecture.The Horton graphs and Ellingham-Horton graphs are examples of 3-connected bicubic graphs that provided counterexamples to the Tutte conjecture.
The Heawood graph is a cubic graph on 14 vertices and 21 edges which is the unique (3,6)-cage graph. It is also a Moore graph. The Heawood graph is also the generalized hexagon , and its line graph is the generalized hexagon . The Heawood graph is illustrated above in a number of embeddings.It has graph diameter 3, graph radius 3, and girth 6. It is cubic symmetric, nonplanar, Hamiltonian, and can be represented in LCF notation as .It has chromatic number 2 and chromaticpolynomialIts graph spectrum is .It is 4-transitive, but not 5-transitive (Harary 1994, p. 173).The Heawood graph is one of eight cubic graphs on 14 nodes with smallest possible graph crossing number of 3 (another being the generalized Petersen graph ), making it a smallest cubic crossing number graph (Pegg and Exoo 2009, Clancy et al. 2019).The Heawood graph corresponds to the seven-color torus map on 14 nodes illustrated above. The Heawood graph is the point/line incidence..
A bicubic graph is a bipartite cubicgraph.Tutte (1971) conjectured that all 3-connected bicubic graphs are Hamiltonian (the Tutte conjecture), but a number of nonhamiltonian bicubic graphs have subsequently been discovered.The numbers of simple bicubic graphs on , 4, ... nodes are 0, 0, 1, 1, 2, 5, 13, 38, 149, ... (OEIS A006823), the first few of which are illustrated above.The following table summarizes some named bicubic graphs.graph utility graph6cubical graph8Franklin graph12Heawood graph14Möbius-Kantor graph16Pappus graph18Desargues graph20truncated octahedral graph24Levi graph30Dyck graph32great rhombicuboctahedral graph48Gray graph54Balaban 10-cage70Foster graph90great rhombicosidodecahedral graph120Tutte 12-cage126
Let be a simple graph with nonsingular (0,1) adjacency matrix . If all the diagonal entries of the matrix inverse are zero and all the off-diagonal entries of are nonzero, then is called a nuciferous graph (Ghorbani 2016).The path graph has adjacency matrix (and adjacency matrix inverse) given bywhich is therefore nuciferous. Initially, this was the only example known, and in fact, no others exist on 10 or fewer nodes (E. Weisstein, Mar. 18, 2016). As a result, it was conjectured by Sciriha et al. (2013) that no others exist.This conjecture was disproved by Ghorbani (2016) who found 21 Cayleygraphs examples on 24, 28, and 30 nodes.
Petersen's theorem states that every cubic graph with no bridges has a perfect matching (Petersen 1891; Frink 1926; König 1936; Skiena 1990, p. 244). In fact, this theorem can be extended to read, "every cubic graph with 0, 1, or 2 bridges has a perfect matching."The graph above shows the smallest counterexample for 3 bridges, namely a connected cubic graph on 16 vertices having no perfect matchings. This graph is implemented in the Wolfram Language as GraphData["Cubic", 16, 14].Errera (1922) strengthened Petersen's theorem by proving that if all bridges of a connected cubic graph lie on a single path of , then has a perfect matching.
A perfect matching of a graph is a matching (i.e., an independent edge set) in which every vertex of the graph is incident to exactly one edge of the matching. A perfect matching is therefore a matching containing edges (the largest possible), meaning perfect matchings are only possible on graphs with an even number of vertices. A perfect matching is sometimes called a complete matching or 1-factor.The nine perfect matchings of the cubical graphare illustrated above.Note that rather confusingly, the class of graphs known as perfectgraphs are distinct from the class of graphs with perfect matchings.Precomputed graphs having a perfect matching return True for GraphData[g, "PerfectMatching"] in the Wolfram Language.While not all graphs have a perfect matching, all graphs do have a maximum independent edge set (i.e., a maximum matching; Skiena 1990, p. 240; Pemmaraju and Skiena 2003, pp. 29 and 343). Furthermore,..
A -matching in a graph is a set of edges, no two of which have a vertex in common (i.e., an independent edge set of size ). Let be the number of -matchings in the graph , with and the number of edges of . Then the matching polynomial is defined by(1)where vertex count of (Ivanciuc and Balaban 2000, p. 92; Levit and Mandrescu 2005) and is the matching number (which satisfies , where is the floor function).The matching polynomial is also known as the acyclic polynomial (Gutman and Trinajstić 1976, Devillers and Merino 2000), matching defect polynomial (Lovász and Plummer 1986), and reference polynomial (Aihara 1976).A more natural polynomial might be the matching-generating polynomial which directly encodes the numbers of independent edge sets of a graph and is defined by(2)but is firmly established. Fortunately, the two are related by(3)(Ellis-Monaghan and Merino 2008; typo corrected), so(4)The matching polynomial is closely..
A matching, also called an independent edge set, on a graph is a set of edges of such that no two sets share a vertex in common.It is not possible for a matching on a graph with nodes to exceed edges. When a matching with edges exists, it is called a perfect matching. When a matching exists that leaves a single vertex unmatched, it is called a near-perfect matching.While not all graphs have perfect matchings, a largest matching (commonly known as a maximum matching or maximum independent edge set) exists for every graph. The size of this maximum matching is called the matching number of and is denoted .The number of matchings in a graph is sometimes called the Hosoyaindex.A maximal independent edge set, which is different from a maximum independent edge set, is a matching that cannot be enlarged by simply adding an edge. Such matchings are easy to compute, but are not necessarily maximum independent edge sets. A maximal independent edge set on a general..
The Hungarian algorithm finds a maximum independent edge set on a graph. The algorithm starts with any matching and constructs a tree via a breadth-first search to find an augmenting path, namely a path that starts and finishes at unmatched vertices whose first and last edges are not in and whose edges alternate being outside and inside . If the search succeeds, the symmetric difference of and the edges in yields a matching with one more edge than . That edge is added, and then another search is performed for a new augmenting path. If the search is unsuccessful, the algorithm terminates and must be the largest-size matching.As an added bonus, the tree data provides a vertex cover.If the tree search is unsuccessful, as it is at the end, then the size of the vertex cover is the same as the size of the matching, which proves that the final matching has the maximum size possible...
The blossom algorithm (Edmonds 1965) finds a maximum independent edge set in a (possibly weighted) graph. While a maximum independent edge set can be found fairly easily for a bipartite graph using the Hungarian maximum matching algorithm, the general case is more difficult. Edmonds's blossom algorithm starts with a maximal independent edge set, which it tries to extend to a maximum independent edge set using the property that a matching is maximum iff the matching does not admit an augmenting path.The blossom algorithm checks for the existence of an augmenting path by a tree search as in the bipartite case, but with special handling for the odd-length cycles that can arise in the general case. Such a cycle is called a blossom. The blossom can be shrunk and the search restarted recursively. If an augmenting path in a shrunken graph is ever found, it can be expanded up through the blossoms to yield an augmenting path in the original; that alternating..
An edge coloring of a graph is a coloring of the edges of such that adjacent edges (or the edges bounding different regions) receive different colors. An edge coloring containing the smallest possible number of colors for a given graph is known as a minimum edge coloring.Finding the minimum edge coloring of a graph is equivalent to finding the minimum vertex coloring of its line graph (Skiena 1990, p. 216).The edge chromatic number gives the minimum number of colors with which a graph can be colored, i.e., the number of colors in a minimum edge coloring.
Martin Gardner (1975) played an April Fool's joke by asserting that the map of 110 regions illustrated above (left figure) required five colors and constitutes a counterexample to the four-color theorem (cf. Wilson 2004, pp. 14-15; Chartrand and Zhang, p. 23, 2008; Posamentier and Lehmann, Fig. 1.13, 2013). However, because the four-color theorem is true (though not proved until 1976), the map must be (and is) four-colorable (right figure above), as demonstrated by the explicitly coloring due Wagon (1998; 1999, pp. 535-536), obtained algorithmically using the Wolfram Language.As stated by Gardner, "As a public service, I shall comment briefly on six major discoveries of 1974 that for one reason or another were inadequately reported to both the scientific community and the public at large. The most sensational of last year's discoveries in pure mathematics was surely the finding of a counterexample to..
The Franklin graph is the 12-vertex cubic graph shown above whose embedding on the Klein bottle divides it into regions having a minimal coloring using six colors, thus providing the sole counterexample to the Heawood conjecture. The graph is implemented in the Wolfram Language as GraphData["FranklinGraph"].It is the 6-crossed prism graph.The minimal coloring of the Franklin graph is illustrated above.The Franklin graph is nonplanar but Hamiltonian. It has LCF notations and .The graph spectrum of the Franklin graph is .
Vizing's theorem states that a graph can be edge-colored in either or colors, where is the maximum vertex degree of the graph. This partitions graphs into two classes, with the ones requiring colors known as class 1, and the ones requiring colors known as class 2 graphs.
Given a map with genus , Heawood showed in 1890 that the maximum number of colors necessary to color a map (the chromatic number) on an unbounded surface is(1)(2)where is the floor function, is the genus, and is the Euler characteristic. This is the Heawood conjecture. In 1968, for any unbounded orientable surface other than the sphere (or equivalently, the plane) and any nonorientable surface other than the Klein bottle, was shown to be not merely a maximum, but the actual number needed (Ringel and Youngs 1968).When the four-color theorem was proven, the Heawood formula was shown to hold also for all orientable and nonorientable unbounded surfaces with the exception of the Klein bottle. For the Klein bottle only, the actual number of colors needed is six--one less than (Franklin 1934; Saaty 1986, p. 45). The Möbius strip, which is a bounded surface, also requires 6 colors, while blind application of the Heawood formula (which is not..
The fractional edge chromatic number of a graph is the fractional analog of the edge chromatic number, denoted by Scheinerman and Ullman (2011). It can be defined as(1)where is the fractional chromatic number of and is the line graph of .There exists a polynomial-time algorithm for computing the fractional edge chromatic number (Scheinerman and Ullman 2011, pp. 86-87).If the edge chromatic number of a graph equals its maximum vertex degree (i.e., if a graph is class 1), then the fractional edge chromatic number also equals . This follows from the general principle for fractional objects that(2)and the fact that(3)(Scheinerman and Ullman 2011, p. 80), so combining gives(4)Therefore, if , .Since any vertex-transitive graph has either a perfect matching (for even vertex degree) or a near-perfect matching (for odd vertex-degree; Godsil and Royle 2001, p. 43) and every vertex-transitive graph has its fractional chromatic..
A vertex coloring is an assignment of labels or colors to each vertex of a graph such that no edge connects two identically colored vertices. The most common type of vertex coloring seeks to minimize the number of colors for a given graph. Such a coloring is known as a minimum vertex coloring, and the minimum number of colors which with the vertices of a graph may be colored is called the chromatic number, denoted .A minimum vertex coloring can be computed using MinimumVertexColoring[g] in the Wolfram Language package Combinatorica` . Brelaz's heuristic algorithm can be used to find a good, but not necessarily minimal, vertex coloring of a graph. It is implemented as BrelazColoring[g] in the Wolfram Language package Combinatorica` .A vertex coloring of a graph with or fewer colors is known as a k-coloring. A graph having a -coloring (and therefore chromatic number ) is said to be a k-colorable graph, while a graph having chromatic number is called..
Let denote the set of all independent sets of vertices of a graph , and let denote the independent sets of that contain the vertex . A fractional coloring of is then a nonnegative real function on such that for any vertex of ,(1)The sum of values of is called its weight, and the minimum possible weight of a fractional coloring is called the fractional chromatic number .The above definition of fractional coloring is equivalent to allowing multiple colors at each vertex, each with a specified weight fraction, such that adjacent vertices contain no two colors alike. For example, while the dodecahedral graph is 3-colorable since the chromatic number is 3 (left figure above; red, yellow, green), it is 5/2-multicolorable since the fractional chromatic number is 5/2 (5 colors-red, yellow, green, blue, cyan-each with weight 1/2, giving ).Note that in fractional coloring, each color comes with a fraction which indicates how much of it is used in the coloring...
The Lovász number of a graph , sometimes also called the theta function of , was introduced by Lovász (1979) with the explicit goal of estimating the Shannon capacity of a graph. Let be a graph and let be the family of real matrices such that if and are adjacent in , where the other elements are unconstrained. Let the eigenvalues of be denoted . Then(1)(Lovász 1979, Knuth 1994, Brimkov et al. 2000).An equivalent definitions considers the family of real matrices such that if or and are adjacent in and other elements unconstrained. Then(2)Despite much work on the problem of determining , finding explicit values for interesting special cases of graphs remains an open problem (Brimkov et al. 2000). However, explicit formulas are known for for several families of simple graphs. For example, for the cycle graph with and odd,(3)(Lovász 1979, Brimkov et al. 2000).Self-complementary vertex-transitive graphs-including..
Let be a fractional coloring of a graph . Then the sum of values of is called its weight, and the minimum possible weight of a fractional coloring is called the fractional chromatic number , sometimes also denoted (Pirnazar and Ullman 2002, Scheinerman and Ullman 2011) or (Larson et al. 1995), and sometimes also known as the set-chromatic number (Bollobás and Thomassen 1979), ultimate chromatic number (Hell and Roberts 1982), or multicoloring number (Hilton et al. 1973). Every simple graph has a fractional chromatic number which is a rational number or integer.The fractional chromatic number of a graph can be obtained using linearprogramming, although the computation is NP-hard.The fractional chromatic number of any tree and any bipartitegraph is 2 (Pirnazar and Ullman 2002).The fractional chromatic number satisfies(1)where is the clique number, is the fractional clique number, and is the chromatic number (Godsil and Royle 2001,..
The cubic graph on 12 nodes and 18 edges illustrated above in a number of embeddings. It is a snark, albeit a trivial one by the usual definition of the snark.It is implemented in the Wolfram Languageas GraphData["TietzeGraph"].Tietze's graph is the unique almost Hamiltonian cubic graph on 12 vertices (Punnim et al. 2007). In fact, it is also maximally nonhamiltonian (Clark and Entringer 1983).Tietze's graph provides a 6-color coloring of the Möbiusstrip as illustrated above.The plots above show the adjacency, incidence, and graph distance matrices for Tietze's graph.
The Kittell graph is a planar graph on 23 nodes and 63 edges that tangles the Kempe chains in Kempe's algorithm and thus provides an example of how Kempe's supposed proof of the four-color theorem fails.It is also an identity graph.The Fritsch graph and Soifergraph provide smaller (and in fact the smallest possible) counterexamples.
Let be a planar graph whose vertices have been properly colored and suppose is colored . Define the -Kempe chain containing to be the maximal connected component of that 1. Contains , and 2. Contains only vertices that are colored with elements from (Gethner and Springer 2003).The illustration above shows a number of graphs that tangle the chains in Kempe's algorithm and thus provides an example of how Kempe's supposed proof of the four-color theorem fails.
The empire problem, also known as the -pire problem) asks for the maximum number of colors needed to color countries such that no two countries sharing a common border have the same color (this is the usual four-color theorem) in the case where each country consists of disjoint regions. Heawood (1890) showed that colors are sufficient, and for the case , 12 colors are also necessary (Gardner 1997; Frederickson 2002, pp. 31-32).
An edge coloring of a graph is a coloring of the edges of such that adjacent edges (or the edges bounding different regions) receive different colors. An edge coloring containing the smallest possible number of colors for a given graph is known as a minimum edge coloring.A (not necessarily minimum) edge coloring of a graph can be computed using EdgeColoring[g] in the Wolfram Language package Combinatorica` .The edge chromatic number gives the minimumnumber of colors with which graph's edges can be colored.
The edge chromatic number, sometimes also called the chromatic index, of a graph is fewest number of colors necessary to color each edge of such that no two edges incident on the same vertex have the same color. In other words, it is the number of distinct colors in a minimum edge coloring.The edge chromatic number of a graph must be at least , the largest vertex degree of the graph (Skiena 1990, p. 216). However, Vizing (1964) and Gupta (1966) showed that any graph can be edge-colored with at most colors. There are therefore precisely two classes of graphs: those with edge chromatic number equal to (class 1 graphs) and those with edge chromatic number equal to (class 2 graphs).By definition, the edge chromatic number of a graph equals the (vertex) chromatic number of the line graph .The edge chromatic number of a graph can be computed using EdgeChromaticNumber[g] in the Wolfram Language package Combinatorica` . Precomputed edge chromatic numbers..
The Soifer graph is a planar graph on 9 nodes that tangles the Kempe chains in Kempe's algorithm and thus provides an example of how Kempe's supposed proof of the four-color theorem fails. As proved by Gethner and Springer, the Soifer graph is the smallest such counterexample (and is smaller than the Kittell graph and Errera graph).It is implemented in the Wolfram Languageas GraphData["SoiferGraph"].
A labeling of (the vertices) of a graph with positive integers taken from the set is said to be -distinguishing if no graph automorphism of preserves all of the vertex labels. Formally, is -distinguishing if for every nontrivial , there exists such that , where is the vertex set of and is the automorphism group of . The distinguishing number of of is then the smallest such that has a labeling that is -distinguishing (Albertson and Collins 1996).Different graphs with the same automorphism group may have different distinguishing numbers. iff is an identity graph. The distinguishing number of a graph and its graph complement are the same.A graph with has distinguishing number (Tymoczko 2005; due to Albertson, Collins, and Kleitman).Special cases are summarized in the following table.complete bipartite graph complete graph cycle graph generalized Petersen graph hypercube graph path graph star graph -triangular graph wheel graph ..
Let , , ..., be a -graph edge coloring of the complete graph , where for each , 2, ..., t, is the spanning subgraph of consisting of all graph edges colored with the th color. The irredundant Ramsey number is the smallest integer such that for any -graph edge coloring of , the graph complement has an irredundant set of size for at least one , ..., . Irredundant Ramsey numbers were introduced by Brewster et al. (1989) and satisfyFor a summary, see Mynhardt (1992).boundsreference6Brewster et al. 19898Brewster et al. 198912Brewster et al. 198915Brewster et al. 199018Chen and Rousseau 1995, Cockayne et al. 199113Cockayne et al. 199213Cockayne and Mynhardt 1994
Let be the number of monochromatic forced triangles (where and are the number of red and blue triangles) in an extremal graph. Thenwhere is a binomial coefficient and is the floor function (Schwenk 1972).
Heule graphs are a set of unit-distance graphs with chromatic number five derived by Marijn Heule in April-May 2018 from the 1581-vertex de Grey Graph (Heule 2018). As of July 2019, they provide the smallest known examples that establish the solution to the Hadwiger-Nelson problem (i.e., the chromatic number of the plane) as 5, 6, or 7. The first of these graphs were discovered in the days and weeks following publication of the de Grey graph and are summarized in the following table, with the 529-vertex graph being discovered more than a year later and after roughly 100,000 CPU-hours of computation (Heule 2019). The first few are illustrated above.vertex countedge countdiscovery date8744461Apr. 14, 20188264273Apr. 16, 20188034144Apr. 30, 20186333166May 6, 20186103000May 14, 20185532722May 30, 20185292670Jul. 1, 2019..
The de Grey graph is the name given here to the 1581-vertex graph presented in de Grey (2018) which demonstrated that the solution to the Hadwiger-Nelson problem (i.e., the chromatic number of the plane) is at least 5. This graph (together with the larger graphs from which it was derived) provided the first known examples of a unit-distance graph with chromatic number 5.Smaller unit-distance graphs with chromatic number 5, here called Heule graphs, were computationally derived from the de Grey graph by Marijn Heule.
Vizing's theorem states that a graph can be edge-colored in either or colors, where is the maximum vertex degree of the graph. A graph with edge chromatic number equal to is known as a class 2 graph.Class 2 graphs include the Petersen graph, complete graphs for , 5, 7, ..., and the snarks.All regular graphs with an odd number of nodes are class 2 by parity. Such graphs automatically have an even number of edges per vertex.A graph is trivially class 2 if the maximum independent edge sets are not large enough to cover all edges. In particular, a graph is trivially class 2 ifwhere is the matching number, the maximum vertex degree, and the edge count of .The following table summarizes some named class 2 graphs.graph triangle graph3pentatope graph5Petersen graph10first Blanuša snark18second Blanuša snark18Robertson graph19flower snark2025-Grünbaum graph25Doyle graph27double star snark30Szekeres snark50McLaughlin graph275The..
The Royle graphs are the two unique simple graphs on eight nodes whose sigma polynomials have nonreal roots (Read and Wilson 1998, p. 265). The sigma polynomials of these graphs are given by(1)(2)respectively, each of which has two nonreal roots (and where the members of each pairs are complex conjugates of each other).The Royle graphs are implemented in the Wolfram Language as GraphData["RoyleGraph1"] and GraphData["RoyleGraph2"].The numbers of simple graphs having this property on , 2, ... vertices are 0, 0, 0, 0, 0, 0, 0, 2, 42, ..., with the 42 such graphs on 9 vertices illustrated above.