Newton's iteration is an algorithm for computing the square root of a number via the recurrence equation(1)where . This recurrence converges quadratically as .Newton's iteration is simply an application of Newton'smethod for solving the equation(2)For example, when applied numerically, the first few iterations to Pythagoras's constant are 1, 1.5, 1.41667, 1.41422, 1.41421, ....The first few approximants , , ... to are given by(3)These can be given by the analytic formula(4)(5)These can be derived by noting that the recurrence can be written as(6)which has the clever closed-form solution(7)Solving for then gives the solution derived above.The following table summarizes the first few convergents for small positive integer OEIS, , ...11, 1, 1, 1, 1, 1, 1, 1, ...2A001601/A0510091, 3/2, 17/12, 577/408, 665857/470832, ...3A002812/A0715791, 2, 7/4, 97/56, 18817/10864, 708158977/408855776, .....
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.
Some computations allow shortcuts which can be used to speed them up. Consider the operation of raising a number to a positive integer power. It is possible, for example, to calculate by multiplying 13 by itself seven times,However, the shortcut of squaring three times considerably speeds up the computation,It is often quite difficult to determine whether a given computation can be sped up by means of such a trick. Computations that cannot be sped up are said to exhibit computational irreducibility.
While many computations admit shortcuts that allow them to be performed more rapidly, others cannot be sped up. Computations that cannot be sped up by means of any shortcut are called computationally irreducible. The principle of computational irreducibility says that the only way to determine the answer to a computationally irreducible question is to perform, or simulate, the computation. Some irreducible computations can be sped up by performing them on faster hardware, as the principle refers only to computation time.According to Wolfram (2002, p. 741), if the behavior of a system is obviously simple--and is say either repetitive or nested--then it will always be computationally reducible. But it follows from the principle of computational equivalence that in practically all other cases it will be computationally irreducible." Here, "practically all" refers to cases that arise naturally or from a simple..
A pairing function is a function that reversibly maps onto , where denotes nonnegative integers. Pairing functions arise naturally in the demonstration that the cardinalities of the rationals and the nonnegative integers are the same, i.e., , where is known as aleph-0, originally due to Georg Cantor. Pairing functions also arise in coding problems, where a vector of integer values is to be folded onto a single integer value reversibly.515202633414101419253236913182423581217112471112345Let(1)then Hopcroft and Ullman (1979, p. 169) define the pairing function(2)(3)illustrated in the table above, where . The inverse may computed from(4)(5)(6)(7)where is the floor function.51522303949604101623314050361117243241237121825331148131926002591420012345The Hopcroft-Ullman function can be reparameterized so that and are in rather than . This function is known as the Cantor function and is given by(8)illustrated in..
Universality is the property of being able to perform different tasks with the same underlying construction just by being programmed in a different way. Universal systems are effectively capable of emulating any other system. Digital computers are universal, but proving that idealized computational systems are universal can be extremely difficult and technical. Nonetheless, examples have been found in many systems, and any system that can be translated into another system known to be universal must itself be universal. Specific universal Turing machines, universal cellular automata (in both one and two dimensions), and universal cyclic tag systems are known, although the smallest universal example is known only in the case of elementary cellular automata (Wolfram 2002, Cook 2004).
A multiway system is a kind of substitution system in which multiple states are permitted at any stage. This accommodates rule systems in which there is more than one possible way to perform an update.A simple example is a string substitution system. For instance, take the rules and the initial condition . There are two choices for how to proceed. Applying the first rule yields the evolution , while applying the second rule yields the evolution . So at the first step, there is a single state (), at the second step there are two states , and at the third step there is a single state .A path through a multiway system arising from a choice of which substitutions to make is called an evolution. Typically, a multiway system will have a large number of possible evolutions. For example, consider strings of s and s with the rule . Then most strings will have more than one occurrence of the substring , and each occurrence leads down another path in the multiway system...
A Chaitin's constant, also called a Chaitin omega number, introduced by Chaitin (1975), is the halting probability of a universal prefix-free (self-delimiting) Turing machine. Every Chaitin constant is simultaneously computably enumerable (the limit of a computable, increasing, converging sequence of rationals), and algorithmically random (its binary expansion is an algorithmic random sequence), hence uncomputable (Chaitin 1975).A Chaitin's constant can therefore be defined as(1)which gives the probability that for any set of instructions, a particular prefix-free universal Turing machine will halt, where is the size in bits of program .The value of a Chaitin constant is highly machine-dependent. In some cases, it can even be proved that not a single bit can be computed (Solovay 2000).Chaitin constants are perhaps the most obvious specific example of uncomputable numbers. They are also known to be transcendental.Calude et..
A causal network is an acyclic digraph arising from an evolution of a substitution system, and representing its history. The illustration above shows a causal network corresponding to the rules (applied in a left-to-right scan) and initial condition (Wolfram 2002, p. 498, fig. a).The figure above shows the procedure for diagrammatically creating a causal network from a mobile automaton (Wolfram 2002, pp. 488-489).In an evolution of a multiway system, each substitution event is a vertex in a causal network. Two events which are related by causal dependence, meaning one occurs just before the other, have an edge between the corresponding vertices in the causal network. More precisely, the edge is a directed edge leading from the past event to the future event.Some causal networks are independent of the choice of evolution, and these are calledcausally invariant...
A set of integers is said to be one-one reducible to a set () if there is a one-one recursive function such that for every ,(1)and(2)Similarly, a set of integers is many-one reducible to set () if there is a recursive function such that for every ,(3)and(4)Here, the two reducibility relations are reflexivity and transitivity.One-one reducibility implies many-one reducibility. Any set reducible to a recursive set is recursive itself. Any set reducible to a recursively enumerable set is recursively enumerable itself. The above facts are commonly used in recursive undecidability proofs done by reduction to nonrecursive sets.Two sets are one-one/many-one equivalent if each of them is one-one/many-one reducible to the other. One-one equivalence, many-one equivalence, and recursive isomorphism are all equivalence relations.If sets and are recursively isomorphic, then they are one-one equivalent and vice versa.If a class (also called..
A multiway system that generates causal networks which are all isomorphic as acyclic digraphs is said to exhibit causal invariance, and the causal network itself is also said to be causally invariant. Essentially, causal invariance means that no matter which evolution is chosen for a system, the history is the same in the sense that the same events occur and they have the same causal relationships. The figures above illustrate two nontrivial substitution systems that exhibit the same causal networks independent of the order in which the rules are applied (Wolfram 2002, pp. 500-501).Whenever two rule hypotheses overlap in an evolution, the corresponding system is not causally invariant. Hence, the simplest way to search for causal invariance is to use rules whose hypotheses can never overlap except trivially. An overlap can involve one or two strings. For example, does not have any overlaps. However, can overlap as , and the set of strings..
The term "recursive function" is often used informally to describe any function that is defined with recursion. There are several formal counterparts to this informal definition, many of which only differ in trivial respects.Kleene (1952) defines a "partial recursive function" of nonnegative integers to be any function that is defined by a noncontradictory system of equations whose left and right sides are composed from (1) function symbols (for example, , , , etc.), (2) variables for nonnegative integers (for example, , , , etc.), (3) the constant 0, and (4) the successor function .For example,(1)(2)(3)(4)defines to be the function that computes the product of and .Note that the equations might not uniquely determine the value of for every possible input, and in that sense the definition is "partial." If the system of equations determines the value of f for every input, then the definition is said to be "total."..
For any constructible function , there exists a function such that for all functions , the following two statements are equivalent: 1. There exists an algorithm such that for all inputs , computes in volume . 2. is constructible and . Here, the volume is the combined number of active edges during all steps, which is the number of state-changes needed to run a certain Turing machine on a particular input.
A Turing machine is called deterministic if there is always at most one instruction associated with a given present internal state/tape state pair . Otherwise, it is called nondeterministic (Itô 1987, p. 137).In prediction theory, let be a weakly stationary process, and let be a subspace spanned by the (with ). If is independent of so that for every , then is said to be deterministic (Itô 1987, p. 1463).
A function is said to be constructible if some algorithm computes it, in binary, within volume , i.e., . Here, the volume is the combined number of active edges during all steps, which is the number of state-changes needed to run a certain Turing machine on a particular input.
As first shown by Meyer and Ritchie (1967), do-loops (which have a fixed iteration limit) are a special case of while-loops. A function that can be implemented using only do-loops is called primitive recursive. (In contrast, a computable function can be coded using a combination of for- and while-loops, or while-loops only.) Examples of primitive recursive functions include power, greatest common divisor, and (the function giving the th prime).The Ackermann function is the simplest example of a well-defined total function that is computable but not primitive recursive, providing a counterexample to the belief in the early 1900s that every computable function was also primitive recursive (Dötzel 1991; Wolfram 2002, p. 907).
Schur's partition theorem lets denote the number of partitions of into parts congruent to (mod 6), denote the number of partitions of into distinct parts congruent to (mod 3), and the number of partitions of into parts that differ by at least 3, with the added constraint that the difference between multiples of three is at least 6. Then (Schur 1926; Bressoud 1980; Andrews 1986, p. 53).The values of for , 2, ... are 1, 1, 1, 1, 2, 2, 3, 3, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 16, 18, ... (OEIS A003105). For example, for , there are nine partitions satisfying these conditions, as summarized in the following table (Andrews 1986, p. 54).15The identity can be established using the identity(1)(2)(3)(4)(5)(Andrews 1986, p. 54). The identity is significantly trickier.
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).
There are no tilings of the equilateral triangle of side length 7 by all the polyhexes of order . There are nine distinct solutions of all the polyhexes of order which tile a parallelogram of base length 7 and side length 4, one of which is illustrated above (Beeler 1972).
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 sorting algorithm which makes passes over a set of elements, in each pass selecting the smallest element and deleting it from the set. This algorithm has running time , compared to for the best algorithms (Skiena 1990, p. 14).
Quicksort is the fastest known comparison-based sorting algorithm (on average, and for a large number of elements), requiring steps. Quicksort is a recursive algorithm which first partitions an array according to several rules (Sedgewick 1978): 1. Some key is in its final position in the array (i.e., if it is the th smallest, it is in position ). 2. All the elements to the left of are less than or equal to . The elements , , ..., are called the "left subfile." 3. All the elements to the right of are greater than or equal to . The elements , ..., are called the "right subfile." Quicksort was invented by Hoare (1961, 1962), has undergone extensive analysis and scrutiny (Sedgewick 1975, 1977, 1978), and is known to be about twice as fast as the next fastest sorting algorithm. In the worst case, however, quicksort is a slow algorithm (and for quicksort, "worst case" corresponds to already sorted).The average time for the algorithm..
Assume that numbered pancakes are stacked, and that a spatula can be used to reverse the order of the top pancakes for . Then the pancake sorting problem asks how many such "prefix reversals" are sufficient to sort an arbitrary stack (Skiena 1990, p. 48).The maximum numbers of flips needed to sort a random stack of , 2, 3, ... pancakes are 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 13, ... (OEIS A058986), with the number of maximal stacks for , 3, ... being 1, 1, 3, 20, 2, 35, 455, ... (OEIS A067607).The following table (OEIS A092113) gives the numbers of stacks of pancakes requiring flips. A flattened version is shown above as a binary plot.0123456781121131221413611351412354820615207919928113327163014954313571903101635For example, the three stacks of four pancakes requiring the maximum of four flips are , , and , which can be ordered using the flip sequences , , and , respectively (illustrated above). Similarly, the two stacks of six pancakes..
A merge sort (or collation sort) is the combination of two or more ordered lists into a single ordered list (Knuth 1998, p. 158). Merge sorting was one of the first methods proposed for computer sorting, and was first proposed by John von Neumann in 1945 (Knuth 1998, p. 159). Variants include two-way, natural two-way, straight two-way, and list merge sorts.The minimum number of comparisons needed for a merge sort of elements for , 2, ... are 0, 1, 3, 5, 7, 10, 13, 16, 19, 22, 26, 30, ... (OEIS A001768). An upper limit is given by the sequence(1)where(2)where is the floor function (Steinhaus 1999, pp. 55-56), or equivalently,(3)giving 0, 1, 3, 5, 8, 11, 14, 17, 21, 25, 29, ... (OEIS A001855).
A qubit (or quantum bit) is the analog of a bit for quantum computation. Unlike an ordinary bit, which may only assume two possible values (usually called 0 and 1), a qubit may assume a continuum of values of the form where and are arbitrary complex numbers satisfying .
The qubit can be represented as a point on a unit sphere called the Bloch sphere. Define the angles and by letting and . Here, is taken to be real, which can always be made real by multiplying by an overall phase factor (that is unobservable). Then is represented by the unit vector (, , ) called the Bloch vector.
In the IEEE 754-2008 standard (referred to as IEEE 754 henceforth), a signaling NaN or sNaN is a NaN which is signaling in the sense of being most commonly returned in conjunction with various exceptions and handling mechanisms defined therefor. This is in contrast to the quiet NaN (qNaN) which rarely signals a floating-point exception of any kind (IEEE Computer Society 2008).Within the framework documentation, it is suggested that sNaNs be implemented in such a way as to afford meaningful representations for uninitialized variables and arithmetic-like enhancements which may naturally fall beyond the scope of the standard. In particular, sNaNs are largely reserved for operands which signal exceptions for nearly every general-computational and signaling-computational operation though, in rare instances, qNaNs may also result from such contexts...
In the IEEE 754-2008 standard (referred to as IEEE 754 henceforth), a quiet NaN or qNaN is a NaN which is quiet in the sense of rarely signaling a floating-point exception. This is in contrast to the signaling NaN (sNaN) which often occurs in conjunction with any number of exceptions and handling mechanisms defined therefor (IEEE Computer Society 2008).Within the framework documentation, it is suggested that qNaNs be implemented in such a way as to afford useful diagnostic information regarding invalid or unavailable data and results. Under the default exception handling mechanisms provided within IEEE 754, any operation which signals an invalid operation exception and for which a floating-point result is expected shall return a quiet NaN; qNaNs may also result from operations not delivering a floating-point result, though in practice, these operations are far more likely to output sNaNs instead...
Partial evaluation is a branch of computer science studying program transformation via specialization. Any function can be specialized by fixing one or more of its inputs to a particular values. The number of inputs to the program resulting from specialization is the initial number of inputs minus the number of inputs whose values are constants. These specialized programs are also called residual programs.Kleene's s-m-n theorem established a theoretical possibility of function specialization. Partial evaluation applies this idea to computer programs. Note that Kleene's theorem does not address the efficiency of specialized functions whereas the goal of partial evaluation is program optimization.Partial evaluation is accomplished by detecting code fragments depending exclusively on specialized variables whose values are fixed and by symbolically precomputing these fragments. The residual program will run faster because..
In the IEEE 754-2008 standard (referred to as IEEE 754 henceforth), NaN (or "not a number") is a symbolic floating-point representation which is neither a signed infinity nor a finite number. In general, NaNs occur as the output of computations which are somehow "indeterminate," e.g., when attempting to compute quantities such as , , or .The use of NaN representations is a relatively new development. Traditionally, the computation of indeterminate quantities such as or was treated as an unrecoverable error which caused a computation to halt. In practice, however, it sometimes makes sense for a computation to continue despite encountering such a scenario; in these situations, unnecessary halting can be avoided by specifying that the computation of expressions like and output NaN rather than halting the program (Goldberg 1991).Ostensibly, a NaN output should carry with it some degree of diagnostic information regarding..
Let be efficiently computable by an algorithm (solving a P-problem). For fixed , view as a function of that maps (or hashes) bits to bits. Let , then is said to be a (pairwise independent) universal hash function if, for distinct and for all ,i.e., maps all distinct independently and uniformly.These functions are easily constructible (Wegman and Carter 1981, Luby 1996).
A public-key cryptography algorithm which uses prime factorization as the trapdoor one-way function. Define(1)for and primes. Also define a private key and a public key such that(2)(3)where is the totient function, denotes the greatest common divisor (so means that and are relatively prime), and is a congruence. Let the message be converted to a number . The sender then makes and public and sends(4)To decode, the receiver (who knows ) computes(5)since is an integer. In order to crack the code, must be found. But this requires factorization of since(6)Both and should be picked so that and are divisible by large primes, since otherwise the Pollard p-1 factorization method or Williams p+1 factorization method potentially factor easily. It is also desirable to have large and divisible by large primes.It is possible to break the cryptosystem by repeated encryption if a unit of has small field order (Simmons and Norris 1977, Meijer 1996), where..
A hash function projects a value from a set with many (or even an infinite number of) members to a value from a set with a fixed number of (fewer) members. Hash functions are not reversible. A hash function might, for instance, be defined as , where , , and is the floor function.Hash functions can be used to determine if two objects are equal (possibly with a fixed average number of mistakes). Other common uses of hash functions are checksums over a large amount of data (e.g., the cyclic redundancy check [CRC]) and finding an entry in a database by a key value. The UNIX c-shell (csh) uses a hash table to store the location of executable programs. As a result adding new executables in a user's search path requires regeneration of the hash table using the rehash command before these programs can be executed without specifying the complete path.To illustrate the use of hash functions in database lookups, consider a database consisting of an array containing..
In database structures, two quantities are generally of interest: the average number of comparisons required to 1. Find an existing random record, and 2. Insert a new random record into a data structure. Some constants which arise in the theory of digital tree searching are(1)(2)(3)(4)(5)(6)(OEIS A065442 and A065443), where is a q-polygamma function. Erdős (1948) proved that is irrational, and is sometimes known as the Erdős-Borwein constant.The expected number of comparisons for a successful search is(7)(8)and for an unsuccessful search is(9)(10)(OEIS A086309 and A086310). Here is the Euler-Mascheroni constant, , , and are small-amplitude periodic functions, and lg is the base 2 logarithm.The variance for searching is(11)(12)(OEIS A086311) and for inserting is(13)(14)(OEIS A086312).The expected number of pairs of twin vacancies in a digital search tree is(15)where(16)(17)(OEIS A086313), which can also be written(18)(Flajolet..
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 set of two numbers or objects linked in some way is said to be a pair. The pair and is usually denoted (, ), and is generally considered to be ordered, making it a 2-tuple. In certain circumstances, pairs are also called brothers or twins.
A pair of quantities (, ) where ordering is significant, so (, ) is considered distinct from (, ) for .
A structure consisting of an ordered set of sorted lists such that the head and tail entries of later lists nest within earlier ones. For example, an encroaching list set for is given by . Encroaching list sets can be computed using EncroachingListSet[l] in the Wolfram Language package Combinatorica` .It is conjectured that the number of encroaching lists associated with a random permutation of size is for sufficiently large (Skiena 1988; Skiena 1990, p. 78).
The unit of information obtained by using the natural logarithm instead of the base-2 logarithm when defining entropy and related information theoretic functions. When is used instead, information content is obtained in the more convenient unit of bits.
A string of length on an alphabet of characters is an arrangement of not necessarily distinct symbols from . There are such distinct strings.For example, the strings of length on the alphabet are , , , , , , , and .In the Wolfram Language, strings of length in the alphabet consisting of the members of a list can be enumerated using Tuples[list, n].
A stack is a data structure which is a special kind of list in which elements may be added to or removed from the top only. These actions are called a push or a pop, respectively. Actions may be taken by popping one or more values, operating on them, and then pushing the result back onto the stack.Stacks are used as the basis for computer languages such as FORTH, PostScript® (Adobe Systems), and the RPN language used in Hewlett-Packard® programmable calculators.Another notion of the term stack is the algebraicgeometry stack of Grothendieck.
A set-like object in which order is ignored, but multiplicity is explicitly significant. Therefore, multisets and are equivalent, but and differ. The number of multisets of length on symbols is called multichoose , denoted .
For a set partition of elements, the -character string in which each character gives the set block (, , ...) in which the corresponding element belongs is called the restricted growth string (or sometimes the restricted growth function). For example, for the set partition , the restricted growth string would be 0122. If the set blocks are "sorted" so that , then the restricted growth string satisfies the inequality for , 2, ..., .
The number of ways a set of elements can be partitioned into nonempty subsets is called a Bell number and is denoted (not to be confused with the Bernoulli number, which is also commonly denoted ).For example, there are five ways the numbers can be partitioned: , , , , and , so ., and the first few Bell numbers for , 2, ... are 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, ... (OEIS A000110). The numbers of digits in for , 1, ... are given by 1, 6, 116, 1928, 27665, ... (OEIS A113015).Bell numbers are implemented in the WolframLanguage as BellB[n].Though Bell numbers have traditionally been attributed to E. T. Bell as a result of the general theory he developed in his 1934 paper (Bell 1934), the first systematic study of Bell numbers was made by Ramanujan in chapter 3 of his second notebook approximately 25-30 years prior to Bell's work (B. C. Berndt, pers. comm., Jan. 4 and 13, 2010).The first few prime Bell numbers occur at indices..
An antimagic square is an array of integers from 1 to such that each row, column, and main diagonal produces a different sum such that these sums form a sequence of consecutive integers. It is therefore a special case of a heterosquare. It was defined by Lindon (1962) and appeared in Madachy's collection of puzzles (Madachy 1979, p. 103), originally published in 1966. Antimagic squares of orders 4-9 are illustrated above (Madachy 1979). For the square, the sums are 30, 31, 32, ..., 39; for the square they are 59, 60, 61, ..., 70; and so on.Let an antimagic square of order have entries 0, 1, ..., , , and letbe the magic constant. Then if an antimagic square of order exists, it is either positive with sums , or negative with sums (Madachy 1979).Antimagic squares of orders one, two, and three are impossible. In the case of the square, there is no known method of proof of this fact except by case analysis or enumeration by computer. There are 18 families of..
Twenty golfers wish to play in foursomes for 5 days. Is it possible for each golfer to play no more than once with any other golfer? The answer is yes, and the following table gives a solution.MonABCDEFGHIJKLMNOPQRSTTueAEIMBJOQCHNTDGLSFKPRWedAGKOBIPTCFMSDHJRELNQThuAHLPBKNSCEORDFIQGJMTFriAFJNBLMRCGPQDEKTHIOSEvent organizers for bowling, golf, bridge, or tennis frequently tackle problems of this sort, unaware of the problem complexity. In general, it is an unsolved problem. A table of known results is maintained by Harvey.
In a boarding school there are fifteen schoolgirls who always take their daily walks in rows of threes. How can it be arranged so that each schoolgirl walks in the same row with every other schoolgirl exactly once a week? Solution of this problem is equivalent to constructing a Kirkman triple system of order . A visualization is shown above. Falcone and Pavone (2011) give a number of attractive visualizations together with a visual proof of the problem.The following table gives one of the 7 distinct (up to permutations of letters) solutions to the problem. SunABCDEFGHIJKLMNOMonADHBEKCIOFLNGJMTueAEMBHNCGKDILFJOWedAFIBLOCHJDKMEGNThuAGLBDJCFMEHOIKNFriAJNBIMCELDOGFHKSatAKOBFGCDNEIJHLM(The table of Dörrie 1965 contains four omissions in which the and entries for Wednesday and Thursday are written simply as .)..
Find the minimum number of subsets in a separating family for a set of elements, where a separating family is a set of subsets in which each pair of adjacent elements is found separated, each in one of two disjoint subsets. For example, the 26 letters of the alphabet can be separated by a family of nine:The problem was posed by Katona (1973) and solved by C. Mao-Cheng in 1982,where is the ceiling function. is nondecreasing, and the values for , 2, ... are 0, 2, 3, 4, 5, 5, 6, 6, 6, 7, ... (OEIS A007600). The values at which increases are 1, 2, 3, 4, 5, 7, 10, 13, 19, 28, 37, ... (OEIS A007601), so , as illustrated in the preceding example.
A separating family is a set of subsets in which each pair of adjacent elements are found separated, each in one of two disjoint subsets. The 26 letters of the alphabet can be separated by a family of 9,The minimal size of the separating family for an -set is 0, 2, 3, 4, 5, 5, 6, 6, 6, 7, 7, 7, ... (OEIS A007600).
A Room square (named after T. G. Room) of order (for even) is an arrangement in an square matrix of objects such that each cell is either empty or holds exactly two different objects. Furthermore, each object appears once in each row and column and each unordered pair occupies exactly one cell. The Room square of order 2 is shown below.1,2The Room square of order 8 is given in the following table.1,85,73,42,63,72,86,14,55,64,13,87,26,75,24,81,32,47,16,35,83,51,27,46,84,62,31,57,8
A two-dimensional affine geometry constructed over a finite field. For a field of size , the affine plane consists of the set of points which are ordered pairs of elements in and a set of lines which are themselves a set of points. Adding a point at infinity and line at infinity allows a projective plane to be constructed from an affine plane. An affine plane of order is a block design of the form (, , 1). An affine plane of order exists iff a projective plane of order exists.
A balanced incomplete block design is called resolvable if there exists a partition of its set of blocks into parallel classes, each of which in turn partitions the set . The partition is called a resolution.
A heterosquare is an array of the integers from 1 to such that the rows, columns, and diagonals have different sums. (By contrast, in a magic square, they have the same sum.) There are no heterosquares of order two, but heterosquares of every odd order exist. They can be constructed by placing consecutive integers in a spiral pattern (Fults 1974, Madachy 1979).An antimagic square is a special case of a heterosquare for which the sums of rows, columns, and main diagonals form a sequence of consecutive integers.
A refinement of a cover is a cover such that every element is a subset of an element .
Proper covers are defined as covers of a set which do not contain the entire set itself as a subset (Macula 1994). Of the five covers of , namely , , , , and , only does not contain the subset and so is the unique proper cover of two elements. In general, the number of proper covers for a set of elements is(1)(2)the first few of which are 0, 1, 45, 15913, 1073579193, ... (OEIS A007537).
A minimal cover is a cover for which removal of any single member destroys the covering property. For example, of the five covers of , namely , , , , and , only and are minimal covers.Similarly, the minimal covers of are given by , , , , , , , and . The numbers of minimal covers of members for , 2, ..., are 1, 2, 8, 49, 462, 6424, 129425, ... (OEIS A046165).Let be the number of minimal covers of with members. Thenwhere is a binomial coefficient, is a Stirling number of the second kind, andSpecial cases include and . The table below gives the a triangle of (OEIS A035348).SloaneA000392A003468A016111A046166A046167A057668112113161412522151903056516130134102540171171966336217735017066420181302530538220229511298346100814988
The two-dimensional finite projective plane over ("of order two"), illustrated above. It is a block design with , , , , and , the Steiner triple system , and the unique configuration. The incidence graph of the Fano plane is the Heawood graph.The connectivity of the Fano plane corresponds to the order-2 two-dimensional Apollonian network.The Fano plane also solves the transylvania lottery, which picks three numbers from the integers 1-14. Using two Fano planes we can guarantee matching two by playing just 14 times as follows. Label the graph vertices of one Fano plane by the integers 1-7, the other plane by the integers 8-14. The 14 tickets to play are the 14 lines of the two planes. Then if is the winning ticket, at least two of are either in the interval [1, 7] or [8, 14]. These two numbers are on exactly one line of the corresponding plane, so one of our tickets matches them.The Lehmers (1974) found an application of the Fano plane for factoring..
The Thomson problem is to determine the stable equilibrium positions of classical electrons constrained to move on the surface of a sphere and repelling each other by an inverse square law. Exact solutions for to 8 are known, but and 11 are still unknown.This problem is related to spherical codes, which are arrangements of points on a sphere such the the minimum distance between any pair of points is maximized.The Thomson problem has been solved exactly for only a few values of such as , 4, 6, and 12, where the equilibrium distributions are the vertices of an equilateral triangle circumscribed about a great circle, a regular tetrahedron, a regular octahedron, and a regular icosahedron, respectively.In reality, Earnshaw's theorem guarantees that no system of discrete electric charges can be held in stable equilibrium under the influence of their electrical interaction alone (Aspden 1987)...
Given matches (i.e., rigid unit line segments), find the number of topologically distinct planar arrangements which can be made (Gardner 1991). In this problem, two matches laid end-to-end with no third match at their meeting point are considered equivalent to a single match, so triangles are equivalent to squares, -match tails are equivalent to 1-match tails, etc.Solutions to the match problem are planar topological graphs on edges, and the first few values for , 1, 3, 5, 10, 19, 39, ... (OEIS A003055).
Given a set of men and women, marry them off in pairs after each man has ranked the women in order of preference from 1 to , and each women has done likewise, . If the resulting set of marriages contains no pairs of the form , such that prefers to and prefers to , the marriage is said to be stable. Gale and Shapley (1962) showed that a stable marriage exists for any choice of rankings (Skiena 1990, p. 245). In the United States, the algorithm of Gale and Shapley (1962) is used to match hospitals to medical interns (Skiena 1990, p. 245).In the rankings illustrated above, the male-optimal stable marriage is 4, 2, 6, 5, 3, 1, 7, 9, 8, and the female-optimal stable marriage is 1, 2, 8, 9, 3, 4, 7, 6, 5. A stable marriage can be found using StableMarriage[m, w] in the Wolfram Language package Combinatorica` ...
Let denote a configuration with points and lines ("blocks") . Then the incidence graph , also called the Levi graph, of a configuration is a bipartite graph with "black" vertices , "white" vertices , and an edge between and iff (Coxeter 1950, Pisanski and Randić 2000).The following table summarizes the incidence graphs of some common configurations.nameconfigurationincidence graphCox configuration-hypercube graphCoxeter configurationNauru graphCremona-Richmond configurationLevi graphDesargues configurationDesargues graphdouble sixesSchläfli double sixes graphFano planeHeawood graphGray configurationGray graphKummer configurationKummer graphMiquel configurationrhombic dodecahedral graphMöbius-Kantor configurationMöbius-Kantor graphPappus configurationPappus graphPasch configurationPasch graphReye configurationReye graphDual configurations..
The configuration of ten lines intersecting three at a time in 10 points which arises in Desargues' theorem.Its incidence graph is the Desarguesgraph.
A configuration of 12 planes and 12 points such that six points lie in every plane and six planes pass through every point. Alternatively, the configuration consists of 16 lines and the same 12 points such that four lines pass through every point and three points lie on every line.The points consist of the eight vertices of a cube together with its center and the three points at infinity where parallel edges of the cube meet. The 12 planes are the six faces of the cube and the six planes passing through diagonally opposite edges. The 16 lines consist of the 12 edges and four space diagonals of the cube.The Reye configuration can be realized without any points at infinity by squashing the cube and bringing the points at infinity to finite positions, as illustrated above.