infobox graph name Pappus graph image Image Pappus graph LS.svg 250px image caption The Pappus graph ... number 2 chromatic index 3 properties Symmetric graph Symmetric br Distance transitive graph Distance transitive br Distance regular graph Distance regular br Cubic graph Cubic br Hamiltonian graph Hamiltonian In the mathematics mathematical field of graph theory , the Pappus graph is a 3 regular graph regular undirected graph with 18 vertices and 27 edges, formed as the Levi graph of the Pappus configuration ref MathWorld urlname PappusGraph title Pappus Graph ref . It is named after Pappus ... the hexagon theorem describing the Pappus configuration. All the cubic graph cubic distance regular graph s are known the Pappus graph is one of the 13 such graphs. ref Brouwer, A. E. Cohen, A. M. and Neumaier, A. Distance Regular Graphs. New York Springer Verlag, 1989. ref The Pappus graph has Crossing number graph theory rectilinear crossing number 5, and is the smallest cubic graph with that crossing number OEIS id A110507 . It has Girth graph theory girth 6, diameter 4, radius 4, chromatic number 2, chromatic index 3 and is both 3 k vertex connected graph vertex connected and 3 k edge connected graph edge connected . The Pappus graph has a chromatic polynomial equal to math x 1 x x ... graph has also been used to refer to a related nine vertex graph ref citation last Kagno first I ... pair of points on the same line this nine vertex graph is 6 regular, and is the complement graph of the union of three disjoint triangle graph s. Algebraic properties The automorphism group of the Pappus graph is a group of order 216. It acts transitively on the vertices, on the edges and on the arcs of the graph. Therefore the Pappus graph is a symmetric graph . It has automorphisms that take any ... graph, referenced as F018A, is the only cubic symmetric graph on 18 vertices. ref Royle, G. http .... Comput. 40, 41 63, 2002. ref The characteristic polynomial of the Pappus graph is math x 3 x 4 x 3 ... more details
infobox graph name Meredith graph image Image Meredith graph.svg 220px image caption The Meredith graph namesake G. H. Meredith vertices 70 edges 140 automorphisms girth 4 diameter 8 radius 7 chromatic number 3 chromatic index 5 properties Eulerian graph Eulerian In the mathematics mathematical field of graph theory , the Meredith graph is a 4 regular graph regular undirected graph with 70 vertices and 140 edges discovered by Guy H. J. Meredith in 1973. ref MathWorld urlname MeredithGraph title Meredith graph ref The Meredith graph is 4 k vertex connected graph vertex connected and 4 k edge connected graph edge connected , has chromatic number 3, chromatic index 5, radius 7, diameter 8, girth 4 and is Hamiltonian graph non hamiltonian . ref Bondy, J. A. and Murty, U. S. R. Graph Theory . Springer, p. 470, 2007. ref Published in 1973, it provides a counterexample to the Crispin Nash Williams conjecture that every 4 regular 4 vertex connected graph is Hamiltonian. ref Meredith, G. H. J. Regular 4 Valent 4 Connected Nonhamiltonian Non 4 Edge Colorable Graphs. J. Combin. Th. B 14, 55 60, 1973. ref ref Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications . New York North Holland, p. 239, 1976. ref However, W. T. Tutte showed that all 4 connected planar graph s are hamiltonian. ref Tutte, W.T., ed., Recent Progress in Combinatorics. Academic Press, New York, 1969. ref The characteristic polynomial of the Meredith graph is math x 4 x 1 10 x 21 x 1 11 x 3 x 2 13 x 6 26 x 4 3 x 3 169 x 2 39 x 45 4 math . Gallery gallery Image Meredith graph 3COL.svg The chromatic number of the Meredith graph is 3. Image Meredith graph 5color edge.svg The chromatic index of the Meredith graph is 5. gallery References reflist Category Individual graphs Category Regular graphs fr Graphe de Meredith ... more details
infobox graph name Franklin Graph image Image Franklin graph hamiltonian.svg 220px image caption The Franklin Graph namesake Philip Franklin vertices 12 edges 18 automorphisms 48 Cyclic group Z 2 Z Symmetric group S sub 4 sub girth 4 radius 3 diameter 3 chromatic number 2 chromatic index 3 properties Cubic graph Cubic br Hamiltonian graph Hamiltonian br Bipartite graph Bipartite br Triangle free graph Triangle free br Perfect graph Perfect br vertex transitive graph Vertex transitive In the mathematics mathematical field of graph theory , the Franklin graph a 3 regular graph with 12 vertices and 18 edges. ref MathWorld urlname FranklinGraph title Franklin Graph ref The Franklin graph is named after Philip Franklin , who disproved the Heawood conjecture on the number of colors needed when a two dimensional surface is partitioned into cells by a graph embedding . ref MathWorld urlname HeawoodConjecture ... graph can be embedded onto the Klein bottle so that it forms a map requiring six colors, showing that six colors are sometimes necessary in this case. It is Hamiltonian graph Hamiltonian and has chromatic number 2, chromatic index 3, radius 3, diameter 3 and girth graph theory girth 4. It is also a 3 k vertex connected graph vertex connected and 3 k edge connected graph edge connected perfect graph . Algebraic properties The Graph automorphism automorphism group of the Franklin graph is of order ... group Z 2 Z and the symmetric group S sub 4 sub . It acts transitively on the vertices of the graph, making it vertex transitive graph vertex transitive . The characteristic polynomial of the Franklin graph is math x 3 x 1 3 x 1 3 x 3 x 2 3 2. math Gallery gallery Image Franklin graph 2COL.svg The chromatic number of the Franklin graph is 2. Image Franklin graph 3color edge.svg The chromatic index of the Franklin graph is 3. Image franklin graph.svg Alternative drawing of the Franklin graph gallery commonscat Franklin graph References reflist DEFAULTSORT Franklin Graph Category ... more details
context date November 2010 In graph theory a process graph is a directed graph directed bipartite graph used in workflow Conceptual model modeling . The vertex graph theory vertices of the graph mathematics graph are of two types, operation O and material M . The two vertex types form two wikt disjunctive disjunctive set mathematics set s. The edge geometry edges of the graph link the O and M vertices. An edge from an operation vertex O connects to a material vertex M if M is the output of O, such as a document material that is output by a write up operation . An edge from M to O indicates that M is an element of the input set of O, e.g. a document may be part of the input to a review operation. References See Wikipedia Footnotes on how to create references using ref ref tags which will then appear here automatically Reflist External links http www.p graph.com wiki index.php Process Graph 28P graph 29 P Graph wiki Categories DEFAULTSORT Process Graph Category Application specific graphs ... more details
infobox graph name Hoffman graph image Image Hoffman graph.svg 220px image caption The Hoffman graph namesake Alan Hoffman mathematician Alan Hoffman vertices 16 edges 32 automorphisms 48 Z 2 Z S sub 4 sub girth 4 diameter 4 radius 4 chromatic number 2 chromatic index 4 properties Hamiltonian graph Hamiltonian ref MathWorld urlname HamiltonianGraph title Hamiltonian Graph ref br Bipartite graph Bipartite br Perfect graph Perfect br Eulerian graph Eulerian In the mathematics mathematical field of graph theory , the Hoffman graph is a 4 regular graph with 16 vertices and 32 edges discovered by Alan Hoffman mathematician Alan Hoffman . ref MathWorld urlname HoffmanGraph title Hoffman graph ref Published in 1963, it is cospectral to the hypercube graph Q sub 4 sub . ref Hoffman, A. J. On the Polynomial of a Graph. Amer. Math. Monthly 70, 30 36, 1963. ref ref van Dam, E. R. and Haemers, W. H. Spectral Characterizations of Some Distance Regular Graphs. J. Algebraic Combin. 15, 189 202, 2003. ref The Hoffman graph has many common properties with the hypercube Q sub 4 sub both are Hamiltonian graph Hamiltonian and have chromatic number 2, chromatic index 4, radius 4, girth 4 and diameter 4. It is also a 4 k vertex connected graph vertex connected graph and a 4 k edge connected graph edge connected graph . Algebraic properties The Hoffman graph is not a vertex transitive graph and its full automorphism group is a group of order 48 isomorphic to the direct product of groups direct product ... graph is equal to math x 4 x 2 4 x 6 x 2 4 x 4 math making it an integral graph a graph whose Spectral graph theory spectrum consists entirely of integers. It is the same spectrum than the hypercube Q sub 4 sub . Gallery gallery Image Hoffman graph hamiltonian.svg The Hoffman graph is Hamiltonian graph Hamiltonian . Image Hoffman graph 2COL.svg The chromatic number of the Hoffman graph is 2. Image Hoffman graph 4color edge.svg The chromatic index of the Hoffman graph is 4. gallery ... more details
infobox graph name Holt graph image File Holt graph.svg 220px image caption In the Holt graph, all vertices ... 3 chromatic number 3 chromatic index 5 properties Vertex transitive graph Vertex transitive br Edge transitive graph Edge transitive br Half transitive graph Half transitive br Hamiltonian graph Hamiltonian br Eulerian graph Eulerian br Cayley graph In the mathematics mathematical field of graph theory , the Holt graph or Doyle graph is the smallest half transitive graph , that is, the smallest example of a Vertex transitive graph vertex transitive and Edge transitive graph edge transitive graph which is not also symmetric graph symmetric . ref Doyle, P. A 27 Vertex Graph That Is Vertex Transitive ..., Handbook of Graph Theory , CRC Press, 2004, ISBN 1584880902, p. 491. ref It is named after Peter G. Doyle and Derek F. Holt, who discovered the same graph independently in 1976 ref citation first P ... . As cited by MathWorld. ref and 1981 ref name holt citation title A graph which is edge transitive but not arc transitive first Derek F. last Holt journal Journal of Graph Theory volume 5 issue 2 pages 201 204 year 1981 doi 10.1002 jgt.3190050210 . ref respectively. The Holt Graph has graph diameter diameter 3, radius 3 and girth graph theory girth 5, chromatic number 3, chromatic index 5 and is Hamiltonian graph Hamiltonian with formatnum 98472 distinct Hamiltonian cycles. ref name Mathworld MathWorld urlname DoyleGraph title Doyle Graph ref It is also a 4 k vertex connected graph vertex connected and a 4 k edge connected graph edge connected graph. It has an graph ... group than a symmetric graph with the same number of vertices and edges would have. The graph drawing ... of the Holt graph is math x 3 6x 2 6 x 2 4 x 1 4 x 4 . math Gallery gallery Image Holt graph 3COL.svg The chromatic number of the Holt graph is 3. Image Holt graph 5color edge.svg The chromatic index of the Holt graph is 5. Image Holt graph hamiltonian.svg The Holt graph is Hamiltonian ... more details
infobox graph image File E7 graph.svg 241px image caption Gosset graph 3 sub 21 sub BR Two vertices coincide in the center of this graph. Edges also coincide with this projection. name Gosset graph namesake Thorold Gosset vertices 56 edges 756 automorphisms 2903040 diameter 3 radius 3 girth 3 properties Distance regular graph br Integral graph Integral br Vertex transitive graph Vertex transitive The Gosset graph , named after Thorold Gosset , is a specific regular graph 1 n skeleton skeleton of the 7 dimensional Gosset 3 21 polytope 3 sub 21 sub polytope with 56 vertices and valency 27. Construction The Gosset graph can be explicitly constructed as follows the 56 vertices are the vectors in R sup 8 sup , obtained by permuting the coordinates and possibly taking the opposite of the vector 3, 3, &minus 1, &minus 1, &minus 1, &minus 1, &minus 1, &minus 1 . Two such vectors are adjacent when their inner product is 8. Properties In the above representation, two vertices are at distance two when their inner product is &minus 8 and at distance three when their inner product is &minus 24 which is only possible if the vectors are each other s opposite . The Gosset graph is Distance regular graph distance regular with diameter three. The Graph automorphism automorphism group of the Gosset graph is isomorphic to the Coxeter group E7 mathematics E sub 7 sub and hence has order 2903040. The Gosset 3 sub 21 sub polytope is a semiregular polytope . Therefore the automorphism group of the Gosset graph, E sub 7 sub , Group action acts transitively upon its vertices, making it a vertex transitive graph . The characteristic polynomial of the Gosset graph is math x 27 x 9 7 x 1 27 x 3 21 . , math Therefore this graph is an integral graph . References MathWorld title Gosset Graph urlname GossetGraph Category Individual graphs Category Regular graphs combin stub fr Graphe de Gosset ... more details
Infobox graph name Diamond graph image Image Diamond graph.svg 170px vertices 4 edges 5 automorphisms 4 Klein four group Z 2 Z Z 2 Z diameter 2 girth 3 radius 1 chromatic number 3 chromatic index 3 properties Hamiltonian graph Hamiltonian br planar graph Planar br unit distance graph Unit distance In the mathematics mathematical field of graph theory , the diamond graph is a planar graph planar undirected graph with 4 vertices and 5 edges. ref MathWorld urlname DiamondGraph title Diamond Graph ref ref ISGCI Information System on Graph Class Inclusions v2.0. http wwwteo.informatik.uni rostock.de isgci smallgraphs.html List of Small Graphs . ref It consists of a complete graph math K 4 math minus one edge. The diamond Graph has radius 1, graph diameter diameter 2, girth graph theory girth 3, chromatic number 3 and chromatic index 3. It is also a 3 k vertex connected graph vertex connected and a 3 k edge connected graph edge connected Graceful labeling graceful ... lee publicat files On Vertex graceful p p 1 Graphs.pdf ref Hamiltonian graph . Diamond free graphs and forbidden minor A graph is diamond free if it has no diamond as an induced subgraph . The triangle free graph s are diamond free graphs, since every diamond contains a triangle. The Hougardy s conjecture ... The family of graphs in which each Connected component graph theory connected component is a cactus graph is downwardly closed under graph minor operations. This graph family may be characterized by a single forbidden minor . This minor is the diamond graph. ref citation last1 El Mallah first1 Ehab ... 354 362 doi 10.1109 31.1748 . ref If both the butterfly graph and the diamond graph are forbidden ... automorphism group of the diamond graph is a group of order 4 isomorphic to the Klein four group , the direct ... polynomial of the diamond graph is math x x 1 x 2 x 4 math . It is the only graph with this characteristic polynomial, making it a graph determined by its spectrum. References reflist Category Individual ... more details
infobox graph name Robertson graph image Image Robertson graph hamiltonian.svg 240px image caption The Robertson graph is Hamiltonian. namesake Neil Robertson mathematician Neil Robertson vertices 19 edges 38 automorphisms 24 dihedral group D sub 12 sub girth 5 diameter 3 radius 3 chromatic number 3 chromatic index 5 ref MathWorld urlname Class2Graph title Class 2 Graph ref properties Cage graph theory Cage br Hamiltonian graph Hamiltonian In the mathematics mathematical field of graph theory , the Robertson graph or 4,5 cage is a 4 regular graph regular undirected graph with 19 vertices and 38 edges named after Neil Robertson mathematician Neil Robertson . ref MathWorld urlname RobertsonGraph title Robertson Graph ref ref Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York North Holland, p. 237, 1976. ref The Robertson graph is the unique cage graph 4,5 cage graph and was discovered by Robertson in 1964. ref Robertson, N. The Smallest Graph of Girth 5 and Valency 4. Bull. Amer. Math. Soc. 70, 824 825, 1964. ref As a cage graph, it is the smallest 4 regular graph with girth 5. It has chromatic number 3, chromatic index 5, diameter 3, radius 3 and is both 4 k vertex connected graph vertex connected and 4 k edge connected graph edge connected . The Robertson graph is also a Hamiltonian graph which possesses formatnum 5376 distinct directed Hamiltonian cycles. Algebraic properties The Robertson graph is not a vertex transitive graph and its full automorphism group is isomorphic to the dihedral group of order 24, the group of symmetries of a regular dodecagon ... cage survey, Electr. J. Combin. 15, 2008. ref The characteristic polynomial of the Robertson graph is math ... Robertson graph.svg The Robertson graph as drawn in the original publication. Image Robertson graph 3COL.svg The chromatic number of the Robertson graph is 3. Image Robertson graph 5color edge.svg The chromatic index of the Robertson graph is 5. gallery References reflist Category Individual ... more details
infobox graph name Ljubljana graph image Image Ljubljana graph hamiltonian.svg 240px image caption The Ljubljana graph is hamiltonian. namesake vertices 112 edges 168 girth 10 radius 7 diameter 8 chromatic number 2 chromatic index 3 automorphisms 168 properties Cubic graph Cubic br Semi symmetric graph Semi symmetric br Hamiltonian graph Hamiltonian In the mathematics mathematical field of graph theory , the Ljubljana graph is an undirected graph undirected bipartite graph with 112 vertex graph theory vertices and 168 edge graph theory edges . ref mathworld urlname LjubljanaGraph title Ljubljana Graph ref It is a cubic graph with diameter 8, radius 7, chromatic number 2 and chromatic index 3 ... 12. ref name LUB Construction The Ljubljana graph is Hamiltonian graph Hamiltonian and can be constructed ..., 39, 33, 9, 51, 51, 47, 33, 19, 51, 21, 29, 21, 31, 39 sup 2 sup . The Ljubljana graph is the Levi graph ... of the Ljubljana graph is a group of order 168. It acts transitively on the edges the graph but not on its vertices there are Graph automorphism symmetries taking every edge to any other edge, but not taking every vertex to any other vertex. Therefore, the Ljubljana graph is a semi symmetric graph , the third smallest possible cubic semi symmetric graph after the Gray graph on 54 vertices and the Iofinova Ivanov graph on 110 vertices. ref Marston Conder, Aleksander Malni , Dragan Maru i and Prim ... polynomial of the Ljubljana graph is math x 3 x 14 x 3 x 2 x 4 7 x 2 2 6 x 2 x 4 7 x 4 6x 2 4 14 . math History The Ljubljana graph was first published in 1993 by Andries Brouwer Brouwer , Dejter ... of a 112 vertices edge but not vertex transitive cubic graph found by R. M. Foster , but unpublished ... vertices graph in 2002 and named it the Ljubljana graph after the capital of Slovenia . ref name LUB Conder, M. Malni , A. Maru i , D. Pisanski, T. and Poto nik, P. The Ljubljana Graph. 2002. http ... but not vertex transitive cubic graph and therefore that was the graph found by Foster. Gallery gallery ... more details
infobox graph name Gray graph image Image Gray graph hamiltonian.svg 240px image caption The Gray graph ... chromatic index 3 automorphisms 1296 properties Cubic graph Cubic br Semi symmetric graph Semi symmetric br Hamiltonian graph Hamiltonian In the mathematics mathematical field of graph theory , the Gray graph is an undirected graph undirected bipartite graph with 54 vertex graph theory vertices and 81 edge graph theory edges . It is a cubic graph every vertex touches exactly three edges. It was discovered ... to a question posed by Jon Folkman 1967. The Gray graph is interesting as the first known example of a cubic graph having the algebraic property of being edge but not vertex transitive see below . The Gray graph has chromatic number 2, chromatic index 3, radius 6 and diameter 6. It is also a 3 k vertex connected graph vertex connected and 3 k edge connected graph edge connected planar graph non planar graph . Construction The Gray graph can be constructed harv Bouwer 1972 from the 27 points of a 3 ... line has exactly three points on it. The Gray graph is the Levi graph of this configuration it has ..., yielding an n valent Levi graph with algebraic properties similar to those of the Gray graph. In Monson,Pisanski,Schulte,Ivic Weiss 2007 , the Gray graph appears as a different sort of Levi graph for the edges ... and Toma Pisanski Pisanski 2000 give several alternative methods of constructing the Gray graph. As with any bipartite graph, there are no odd length cycle graph theory cycles , and there are also no cycles of four or six vertices, so the girth graph theory girth of the Gray graph is 8. The simplest oriented surface on which the Gray graph can be embedded has genus 7 harv Maru i Pisanski Wilson 2005 . The Gray graph is Hamiltonian graph Hamiltonian and can be constructed from the LCF notation math 25,7, 7,13, 13,25 9. math Algebraic properties The automorphism group of the Gray graph is a group of order 1296. It acts transitively on the edges the graph but not on its vertices there are Graph ... more details
infobox graph name Wagner graph image Image Wagner graph ham.svg 220px image caption The Wagner graph ... properties Cubic graph Cubic br Hamiltonian graph Hamiltonian br Triangle free graph Triangle free br Vertex transitive graph Vertex transitive br Toroidal graph Toroidal br Apex graph Apex In the mathematics mathematical field of graph theory , the Wagner graph is a 3 regular graph with 8 vertices ... Graph Theory year 2007 publisher Springer isbn 9781846289699 pages 275 276 ref It is the 8 vertex M bius ladder graph. Properties As a M bius ladder, the Wagner graph is Planar graph nonplanar but has Crossing number graph theory crossing number one, making it an apex graph . It can be embedded without crossings on a torus or projective plane , so it is also a toroidal graph . It has girth 4, diameter 2, radius 2, chromatic number 3, chromatic index 3 and is both 3 k vertex connected graph vertex connected and 3 k edge connected graph edge connected . The Wagner graph has 392 spanning tree s it and the complete graph K sub 3,3 sub have the most spanning trees among all cubic graphs with the same ... problems in graph theory year 1999 eprint math.CO 9907050 postscript . ref The Wagner graph is a vertex transitive graph but is not edge transitive graph edge transitive . Its full automorphism group ... , including both rotations and reflections. The characteristic polynomial of the Wagner graph is math x 3 x 1 2 x 1 x 2 2x 1 2 math . It is the only graph with this characteristic polynomial, making it a graph determined by its spectrum. The Wagner graph is triangle free graph triangle free and has ... n such that any n vertex graph contains either a triangle or a four vertex independent set is ... Springer Verlag isbn 9780387746401 page 245 postscript . . ref Graph minors M bius ladders play an important role in the theory of Minor graph theory graph minors . The earliest result of this type ... doi 10.1007 BF01594196 postscript . ref For this reason M sub 8 sub is called the Wagner graph. The Wagner ... more details
Graph transformation , or Graph rewriting , concerns the technique of creating a new graph mathematics graph out of an original graph using some automatic machine. It has numerous applications, ranging from Formal verification software verification to layout algorithm s. Graph transformations can be used ... as a graph, further steps in that computation can then be represented as transformation rules on that graph. Such rules consist of an original graph, which is to be matched to a subgraph in the complete state, and a replacing graph, which will replace the matched subgraph. Formally, a graph mathematics graph rewriting system consists of a set of graph rewrite rules of the form math L rightarrow R math , with math L math being called pattern graph or left hand side and math R math being called replacement graph or right hand side of the rule . A graph rewrite rule is applied to the host graph by searching for an occurrence of the pattern graph pattern matching , thus solving the subgraph isomorphism problem and by replacing the found occurrence by an instance of the replacement graph. Sometimes graph grammar is used as a synonym for graph rewriting system, especially in the context of formal ... some starting graph, i.e. describing a graph language instead of transforming a given state host graph into a new state. Graph rewriting approaches There are several approaches to graph rewriting. One ... . From the perspective of the DPO approach a graph rewriting rule is a pair of morphism s in the category of graphs with total graph morphism s as arrows math r L leftarrow K rightarrow R math or math L supseteq K subseteq R math where math K rightarrow L math is injective . The graph K is called invariant or sometimes the gluing graph . A rewriting step or application of a rule r to a host graph ... math k colon K rightarrow G math this is where the name double pushout comes from . Another graph morphism ... graph G where K serves as some kind of interface. In contrast a graph rewriting rule of the SPO approach ... more details
infobox graph name Errera graph image Image Errera graph alt.svg 220px image caption The Errera graph namesake Alfred Errera vertices 17 edges 45 automorphisms 20 dihedral group D sub 10 sub girth 3 radius 3 diameter 4 chromatic number 4 chromatic index 6 properties Planar graph Planar br Hamiltonian graph Hamiltonian ref MathWorld urlname HamiltonianGraph title Hamiltonian Graph ref In the mathematics mathematical field of graph theory , the Errera graph is a graph with 17 vertices and 45 edges discovered by Alfred Errera. ref MathWorld urlname ErreraGraph title Errera graph ref Published in 1921, it provides an example of how Alfred Kempe Kempe s proof of the four color theorem cannot work. ref Errera, A. Du coloriage des cartes et de quelques questions d analysis situs. Ph.D. thesis. 1921. ref ref Peter Heinig. http www m9.ma.tum.de foswiki pub Allgemeines PeterHeinig erreraGraphIsNarrowProof.pdf Proof that the Errera Graph is a narrow Kempe Impasse . 2007. ref Later, the Fritsch graph and Soifer graph provide two smaller counterexamples. ref Gethner, E. and Springer, W. M. II. How False Is Kempe s Proof of the Four Color Theorem? Congr. Numer. 164, 159 175, 2003. ref The Errera graph is Planar graph planar and has chromatic number 4, chromatic index 6, radius 3, diameter 4 and girth graph theory girth 3. All its vertices are of degree 5 or 6 and it is a 5 k vertex connected graph vertex connected graph and a 5 k edge connected graph edge connected graph . Algebraic properties The Errera graph is not a vertex transitive graph and its full automorphism group is isomorphic .... The characteristic polynomial of the Errera graph is math x 2 2 x 5 x 2 x 1 2 x 3 4 x 2 9 x 10 x 4 2 x 3 7 x 2 18 x 9 2 math . Gallery gallery Image Errera graph 4COL.svg The chromatic number of the Errera graph is 4. Image Errera graph 6color edge.svg The chromatic index of the Errera graph is 6. Image Errera graph.svg The Errera graph is Planar graph planar . gallery References ... more details
infobox graph name Foster graph image Image Foster graph.svg 240px image caption The Foster graph namesake ... 4320 girth 10 diameter 8 radius 8 properties Cubic graph Cubic br symmetric graph Symmetric br Hamiltonian graph Hamiltonian br Distance transitive graph Distance transitive In the mathematics mathematical field of graph theory , the Foster graph is a 3 regular graph with 90 vertices and 135 edges. ref MathWorld urlname FosterGraph title Foster Graph ref The Foster graph is Hamiltonian graph Hamiltonian and has chromatic number 2, chromatic index 3, radius 8, diameter 8 and girth graph theory girth 10. It is also a 3 k vertex connected graph vertex connected and 3 k edge connected graph edge connected graph. All the cubic graph cubic distance regular graph s are known. ref Brouwer ... The Foster graph is one of the 13 such graphs. It is the unique Distance transitive graph distance transitive graph with intersection array 3,2,2,2,2,1,1,1 1,1,1,1,2,2,2,3 . ref http www.win.tue.nl aeb ... graph of the partial linear space which is the unique triple Covering space cover with no 8 gons of the generalized quadrangle Tutte Coxeter graph GQ 2,2 . It is named after R. M. Foster , whose Foster census of cubic graph cubic symmetric graph s included this graph. Algebraic properties The automorphism group of the Foster graph is a group of order 4320. ref Royle, G. http www.csse.uwa.edu.au ... and on the arcs of the graph. Therefore the Foster graph is a symmetric graph . It has automorphisms ... , the Foster graph, referenced as F90A, is the only cubic symmetric graph on 90 vertices. ref .... Comput. 40, 41 63, 2002. ref The characteristic polynomial of the Foster graph is equal to math x 3 x 2 9 x 1 18 x 10 x 1 18 x 2 9 x 3 x 2 6 12 math . Gallery gallery Image Foster graph colored.svg Foster graph colored to highlight various cycles. Image Foster graph 2COL.svg The chromatic number of the Foster graph is 2. Image Foster graph 3color edge.svg The chromatic index of the Foster graph ... more details
infobox graph name McGee Graph image Image McGee graph hamiltonian.svg 220px image caption The McGee Graph namesake W. F. McGee vertices 24 edges 36 automorphisms 32 ref name Mathworld girth 7 ref name ... 3 ref name Mathworld properties Cubic graph Cubic br Cage graph theory Cage br Hamiltonian graph Hamiltonian In the mathematics mathematical field of graph theory , the McGee Graph or the 3 7 cage is a 3 regular graph with 24 vertices and 36 edges. ref name Mathworld MathWorld urlname McGeeGraph title McGee Graph ref The McGeeGraph is the unique 3,7 cage graph cage the smallest cubic graph of girth 7 . It is also the smallest cubic cage that is not a Moore graph . First discovered by Sachs but unpublished .... Boll. Un. Mat. Ital. 15, 522 528, 1960 ref the graph is named after McGee who published the result in 1960. ref McGee, W. F. A Minimal Cubic Graph of Girth Seven. Canad. Math. Bull. 3, 149 152, 1960 ref Then, the McGee graph was the proven the unique 3,7 cage by Tutte in 1966. ref Tutte, W. T. Connectivity .... J. Graph Th. 6, 1 22, 1982 ref ref Brouwer, A. E. Cohen, A. M. and Neumaier, A. Distance Regular ... 1 8 are known OEIS id A110507 . The smallest 8 crossing graph is the McGee graph. There exists 5 ... Number Graphs. Mathematica J. 11, 2009 ref One of them is the generalized Petersen graph nobr G 12,5 , also known as the Nauru graph . ref MathWorld urlname GraphCrossingNumber title Graph Crossing ... a 3 k vertex connected graph vertex connected and a 3 k edge connected graph edge connected graph. Algebraic properties The characteristic polynomial of the McGeeGraph graph is math x 3 x 3 x 2 3 x 1 2 x 2 x 2 x 4 x 3 x 2 4x 2 4 math . The automorphism group of the McGee graph is of order 32 and doesn ... is the smallest cubic cage that is not a vertex transitive graph . ref Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York North Holland, p. 237, 1976. ref Gallery gallery Image McGee graph crossing number.svg The Crossing number graph theory crossing number of the McGee ... more details
Infobox graph name Gewirtz graph image Image Gewirtz graph embeddings.svg 300px image caption Some embeddings with 7 fold symmetry. No 8 fold or 14 fold symmetry are possible. vertices 56 edges 280 automorphisms formatnum 80640 radius 2 diameter 2 girth 4 chromatic number 4 properties Strongly regular graph Strongly regular br Hamiltonian graph Hamiltonian br Triangle free graph Triangle free br Vertex transitive graph Vertex transitive br edge transitive graph Edge transitive br distance transitive graph Distance transitive . The Gewirtz graph is a strongly regular graph with 56 vertices and valency 10. It is named after the mathematician Allan Gewirtz, who described the graph in his dissertation. ref http genealogy.math.ndsu.nodak.edu id.php?id 35587 Allan Gewirtz , Graphs with Maximal Even Girth , Ph.D. Dissertation in Mathematics, City University of New York, 1967. ref Construction The Gewirtz graph can be constructed as follows. Consider the unique S 3, 6, 22 Steiner system , with 22 elements and 77 blocks. Choose a random element, and let the vertices be the 56 blocks not containing it. Two blocks are adjacent when they are disjoint. With this construction, one can embed the Gewirtz graph in the Higman Sims graph . Algebraic properties The characteristic polynomial of the Gewirtz graph is math x 10 x 2 35 x 4 20 . , math Therefore it is an integral graph . The Gewirtz graph is also determined by its spectrum. Note Reflist References MathWorld title Gewirtz graph urlname GewirtzGraph Category Individual graphs Category Regular graphs fr Graphe de Gewirtz ... more details
infobox graph name Dyck graph image Image Dyck graph hamiltonian.svg 250px image caption The Dyck graph ... 2 chromatic index 3 properties Symmetric graph Symmetric br Cubic graph Cubic br Hamiltonian graph Hamiltonian br Bipartite graph Bipartite br Cayley graph In the mathematics mathematical field of graph theory , the Dyck graph is a 3 regular graph with 32 vertices and 48 edges, named after Walther ... volume 17 year 1881 . ref ref MathWorld urlname DyckGraph title Dyck Graph ref It is hamiltonian graph Hamiltonian with 120 distinct Hamiltonian cycles. It has chromatic number 2, chromatic index 3, radius 5, diameter 5 and girth graph theory girth 6. It is also a 3 k vertex connected graph vertex connected and a 3 k edge connected graph edge connected graph. The Dyck graph is a toroidal graph , and the dual of its symmetric toroidal embedding is the Shrikhande graph , a strongly regular graph both symmetric and hamiltonian. Algebraic properties The automorphism group of the Dyck graph is a group ... It acts transitively on the vertices, on the edges and on the arcs of the graph. Therefore the Dyck graph is a symmetric graph . It has automorphisms that take any vertex to any other vertex and any edge to any other edge. According to the Foster census , the Dyck graph, referenced as F32A, is the only cubic symmetric graph on 32 vertices. ref citation last1 Conder first1 M. last2 Dobcs nyi first2 ... vertices volume 40 year 2002 . ref The characteristic polynomial of the Dyck graph is equal to math x 3 x 1 9 x 1 9 x 3 x 2 5 6 math . Dyck map The Dyck graph is the skeleton topology skeleton of a Regular map graph theory symmetric tessellation of a surface of genus topology genus three by twelve octagons, known as the Dyck map or Dyck tiling . The dual graph for this tiling is the complete bipartite graph complete tripartite graph K sub 4,4,4 sub . ref citation last Dyck first W. author link ... gallery Image Dyck graph.svg Alternative drawing of the Dyck graph. Image Dyck graph 2COL.svg The chromatic ... more details
infobox graph name Tietze s graph image Image Tietze s graph.svg 220px image caption The Tietze s graph namesake vertices 12 edges 18 chromatic index 4 chromatic number 3 automorphisms 12 Dihedral Group D sub 6 sub girth 3 diameter 3 properties Cubic graph Cubic br Snark graph theory Snark In the mathematics mathematical field of graph theory , the Tietze s graph is an undirected graph undirected cubic graph with 12 vertices and 18 edges, formed by applying a Y transform to the Petersen graph and thereby replacing one of its vertices by a triangle . ref name CE citation first1 L. last1 Clark first2 R. last2 Entringer title Smallest maximally nonhamiltonian graphs journal Periodica Mathematica ... TietzesGraph title Tietze s Graph ref Tietze s graph has chromatic number 3, chromatic index 4, girth ... the Petersen graph it is maximally nonhamiltonian it has no Hamiltonian cycle , but any two vertices can be connected by a Hamiltonian path. ref name CE It and the Petersen graph are the only k vertex connected graph 2 vertex connected cubic non Hamiltonian graphs with 12 or fewer vertices. ref citation ... ref Tietze s graph matches part of the definition of a Snark graph theory snark it is a cubic bridgeless graph that is not 3 edge colorable. However, some authors restrict snarks to graphs without 3 cycles and 4 cycles, and under this more restrictive definition Tietze s graph is not a snark. Tietze s graph is isomorphic to the graph J sub 3 sub , part of an infinite family of flower snark s introduced ... Gallery gallery Image Tietze s graph 3COL.svg The chromatic number of the Tietze s graph is 3. Image Tietze s graph 4color edge.svg The chromatic index of the Tietze s graph is 4. Image Tietze graph mobius.png The Tietze graph can be drawn on a M bius strip with no crossings. ref citation author1 ... Graph Theory with Applications location New York publisher North Holland year 1976 contribution ... commonscat Tietze s graph Notes reflist Category Individual graphs Category Regular graphs fr Graphe ... more details
about the mathematical concept statistical presentation method line chart In graph theory , the line graph L G of undirected graph G is another graph L G that represents the adjacencies between edge graph theory edges of G . The name line graph comes from a paper by harvtxt Harary Norman 1960 although ... Beineke 1978 p 273 . ref Other terms used for the line graph include edge graph , ref name ... the covering graph , ref name Hemminger Beineke 237 the derivative , ref name Hemminger Beineke 237 the edge to vertex dual , ref name Hemminger Beineke 237 the interchange graph , ref name Balakrishnan 44 the adjoint graph , ref name Balakrishnan 44 the conjugate , ref name Hemminger Beineke 237 the derived graph , ref name Balakrishnan 44 and the representative graph . ref name Hemminger Beineke ... graph. In other words, with that one exception, the entire graph can be deduced from knowing the adjacencies of edges lines . Formal definition Given a graph G , its line graph L G is a graph such that each vertex graph theory vertex of L G represents an edge of G and two vertices of L G are adjacent ... graph of the edges of G , representing each edge by the set of its two endpoints. Examples Example construction The following figures show a graph left, with blue vertices and its line graph right, with green vertices . Each vertex of the line graph is shown labeled with the pair of endpoints of the corresponding edge in the original graph. For instance, the green vertex on the right ... 1 in the blue graph and 4,3 corresponding to an edge sharing the endpoint 3 in the blue graph . gallery widths 135px heights 135px File Line graph construction 1.svg Graph G File Line graph construction 2.svg Vertices in L G constructed from edges in G File Line graph construction 3.svg Added edges in L G File Line graph construction 4.svg The line graph L G gallery Line graphs of convex polyhedra A source of examples from geometry are the line graphs of the graphs of cubic graph simple ... more details
infobox graph name Knight s graph image Image Knight s graph.svg 180px image caption 8x8 Knight s graph vertices nm edges 4 mn 6 m n 8 chromatic number chromatic index girth 4 if n 3, m 5 properties In graph theory , a knight s graph , or a knight s tour graph , is a Graph mathematics graph that represents all legal moves of the knight chess knight chess chess piece piece on a chessboard where each vertex represents a square on a chessboard and each edge is a legal move. More specifically, an math n times m math knight s tour graph is a knight s tour graph of an math n times m math chessboard. For a math n times m math knight s tour graph the total number of vertices is simply font face times size 1 nm font . For a math n times n math knight s tour graph the total number of vertices is simply font face times size 1 n sup 2 sup font and the total number of edges is font face times size 1 4 n 2 n 1 font . Additionally, the number of edges for various font face times size 1 n font is identified as OEIS2C id A033996 in the On Line Encyclopedia of Integer Sequences . A Hamiltonian path on the knight s tour graph is a knight s tour . The following Knight s graph shows the number of possible moves that can be made from each position on an 8 8 chessboard. Image Knight s graph showing number of possible moves.svg 500px Knight s graph showing the number of possible moves edges that can be made from each node. See also King s graph Rook s graph Schwenk s theorem Category Mathematical chess problems Category Parametric families of graphs ... more details
In the mathematical discipline of graph theory , a biconnected graph is a connected graph mathematics graph with no Articulation vertex articulation vertices . In other words, a biconnected graph is connected and nonseparable , meaning that if any vertex graph theory vertex were to be removed, the graph will remain connected. The property of being K vertex connected graph 2 connected is equivalent to biconnectivity, with the caveat that the complete graph of two vertices is sometimes regarded as biconnected but not 2 connected. This property is especially useful in maintaining a graph with a two fold Redundancy engineering redundancy , to prevent disconnection upon the removal of a single edge graph theory edge or connection . The use of biconnected graphs is very important in the field of networking see Network flow , because of this property of redundancy. Definition A biconnected undirected graph is a connected graph that is not broken into disconnected pieces by deleting any single vertex and its incident edges . A biconnected directed graph is one such that for any two vertices v and w there are two directed paths from v to w which have no vertices in common other than v and w . class wikitable style text align center Nonseparable or 2 connected graphs or blocks with n nodes OEIS id A002218 Vertices Number of Possibilities 1 0 2 1 3 1 4 3 5 10 6 56 7 468 8 7123 9 194066 10 9743542 11 900969091 12 153620333545 13 48432939150704 14 28361824488394169 15 30995890806033380784 16 63501635429109597504951 17 244852079292073376010411280 18 1783160594069429925952824734641 19 24603887051350945867492816663958981 Examples http mathworld.wolfram.com images eps gif BiconnectedGraphs 1000.gif See also Biconnected component References Eric W. Weisstein. Biconnected Graph. From MathWorld ... graph , in Dictionary of Algorithms and Data Structures online , Paul E. Black, ed., U.S. National ... dads HTML biconnectedGraph.html Category Graph families Category Graph connectivity fa ... more details
about sets of vertices connected by edges graphs of mathematical functions Graph of a function statistical graphs Chart further Graph theory Image 6n graf.svg thumb 250px A graph drawing drawing of a labeled graph on 6 vertices and 7 edges. In mathematics , a graph is an abstract representation of a set ... by mathematical abstractions called Vertex graph theory vertices , and the links that connect some pairs of vertices are called edges . Typically, a graph is depicted in diagrammatic form ... graph symmetric . For example, if the vertices represent people at a party, and there is an edge between two people if they shake hands, then this is an undirected graph, because if person A shook ... B, then this graph is directed, because knowledge of someone is not necessarily a symmetric ... type of graph is called a directed graph and the edges are called directed edges or arcs ... subject studied by graph theory . The word graph was first used in this sense by James Joseph Sylvester J.J. Sylvester in 1878. ref Cite book title Handbook of graph theory first1 Jonathan L. last1 Gross ... http books.google.com ?id mKkIGIea BkC postscript None ref Definitions Definitions in graph theory .... Graph Image Multigraph.svg thumb 125px A general example of a graph actually, a pseudograph ... and Kawada, 69 J , p. 234 or Biggs, p. 4. ref a graph is an ordered pair G V , ..., this type of graph may be described precisely as graph mathematics Undirected graph undirected and graph mathematics Simple graph simple . Other senses of graph stem from different conceptions of the edge ... of the edge. A vertex may exist in a graph and not belong to an edge. V and E are usually taken ... graphs because many of the arguments fail in the infinite graph infinite case . The order of a graph is math V math the number of vertices . A graph s size is math E math , the number of edges. The degree ... at both ends a loop graph theory loop is counted twice. For an edge u , v , graph theorists ... more details
Graph search algorithm Graph traversal refers to the problem of visiting all the nodes in a graph mathematics graph in a particular manner. Tree traversal is a special case of graph traversal. In contrast to tree traversal, in general graph traversal, each node may have to be visited more than once, and a root like node that connects to all other nodes might not exist. Depth first Search A Depth first search DFS is a technique for traversing a finite undirected graph. DFS visits the child nodes before visiting the sibling nodes, that is, it traverses the depth of the tree before the breadth. That called DFS. Usually a stack is used in the search process. Breadth first Search A Breadth first search BFS is another technique for traversing a finite undirected graph. BFS visits the sibling nodes before visiting the child nodes. Usually a queue is used in the search process. Category Graph algorithms combin stub de Suchverfahren Suche in Graphen fa fr Parcours de graphe ko ... more details
A moral graph is a concept in graph theory , used to find the equivalent undirected form of a directed acyclic graph . It is a key step of the junction tree algorithm , used in belief propagation on graphical models . The moralized counterpart of a directed acyclic graph is formed by connecting nodes that have a common child, and then making all edges in the graph undirected. The name stems from the fact the two nodes that have a common child are said to be married . Equivalently, a moral graph of a directed acyclic graph G is an undirected graph in which each node of the original G is now connected to its Markov blanket . Image MoralGraph DAG1.png frame left A directed acyclic graph . Image Moralized graph1.png frame none The corresponding moral graph. The newly added arcs are shown in red in the moralized graph. See also D separation Tree decomposition References cite book last Cowell first Robert G. coauthors Philip Dawid Dawid, A. Philip Lauritzen, Steffen L., David Spiegelhalter Spiegelhalter, David J. title Probabilistic Networks and Expert Systems publisher Springer Verlag New York year 1999 isbn 0 387 98767 3 chapter 3.2.1 Moralization pages 31 33 http staff.utia.cas.cz studeny e3.html M. Studeny On mathematical description of probabilistic conditional independence structures Category Bayesian networks Category Graphical models Category Graph operations compu sci stub ... more details
Encyclopedia
top
