|
Robertson Graph
In the mathematical field of graph theory, the Robertson graph or (4,5)-cage, is a 4- regular undirected graph with 19 vertices and 38 edges named after Neil Robertson. The Robertson graph is the unique (4,5)-cage graph and was discovered by Robertson in 1964. 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- vertex-connected and 4- edge-connected. It has book thickness 3 and queue number 2.Jessica Wolz, ''Engineering Linear Layouts with SAT''. Master Thesis, University of Tübingen, 2018 The Robertson graph is also a Hamiltonian graph which possesses distinct directed Hamiltonian cycles. The Robertson graph is one of the smallest graphs with cop number 4.Turcotte, J., & Yvon, S. (2021). 4-cop-win graphs have at least 19 vertices. Discrete Applied Mathematics, 301, 74-98. Algebraic properties The Robertson graph is not a vertex-transitive graph and its full automorphism group is ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Robertson Graph Hamiltonian
Robertson may refer to: People * Robertson (surname) (includes a list of people with this name) * Robertson (given name) * Clan Robertson, a Scottish clan * Robertson, stage name of Belgian magician Étienne-Gaspard Robert (1763–1837) Places Australia * Division of Robertson, electoral district in the Australian House of Representatives, in New South Wales * Robertson, New South Wales * Robertson, Queensland * Robertson Barracks, an Australian Army base near Darwin, Northern Territory United States * Robertson Boulevard (Los Angeles), California * Robertson Gymnasium, University of California, Santa Barbara * Robertson Field (Connecticut), a public airport * Robertson County, Kentucky * Robertson Field (North Dakota), a public airport * Robertson Tunnel, Portland, Oregon, a light rail transit tunnel * Robertson County, Tennessee * Robertson County, Texas * Robertson Stadium, University of Houston, Houston, Texas * Robertson's Colony, Texas * Robertson, Wyoming Elsewhere * Cap ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Chromatic Index
In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most different colors, for a given value of , or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three. By Vizing's theorem, the number of colors needed to edge color a simple graph is either its maximum degree or . For some graphs, such as bipartite graphs and high-degree planar graphs, the number of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Characteristic Polynomial
In linear algebra, the characteristic polynomial of a square matrix is a polynomial which is invariant under matrix similarity and has the eigenvalues as roots. It has the determinant and the trace of the matrix among its coefficients. The characteristic polynomial of an endomorphism of a finite-dimensional vector space is the characteristic polynomial of the matrix of that endomorphism over any base (that is, the characteristic polynomial does not depend on the choice of a basis). The characteristic equation, also known as the determinantal equation, is the equation obtained by equating the characteristic polynomial to zero. In spectral graph theory, the characteristic polynomial of a graph is the characteristic polynomial of its adjacency matrix. Motivation In linear algebra, eigenvalues and eigenvectors play a fundamental role, since, given a linear transformation, an eigenvector is a vector whose direction is not changed by the transformation, and the corresponding eigenva ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Dodecagon
In geometry, a dodecagon or 12-gon is any twelve-sided polygon. Regular dodecagon A regular dodecagon is a figure with sides of the same length and internal angles of the same size. It has twelve lines of reflective symmetry and rotational symmetry of order 12. A regular dodecagon is represented by the Schläfli symbol and can be constructed as a truncated hexagon, t, or a twice-truncated triangle, tt. The internal angle at each vertex of a regular dodecagon is 150°. Area The area of a regular dodecagon of side length ''a'' is given by: :\begin A & = 3 \cot\left(\frac \right) a^2 = 3 \left(2+\sqrt \right) a^2 \\ & \simeq 11.19615242\,a^2 \end And in terms of the apothem ''r'' (see also inscribed figure), the area is: :\begin A & = 12 \tan\left(\frac\right) r^2 = 12 \left(2-\sqrt \right) r^2 \\ & \simeq 3.2153903\,r^2 \end In terms of the circumradius ''R'', the area is: :A = 6 \sin\left(\frac ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Vertex-transitive Graph
In the mathematical field of graph theory, a vertex-transitive graph is a graph in which, given any two vertices and of , there is some automorphism :f : G \to G\ such that :f(v_1) = v_2.\ In other words, a graph is vertex-transitive if its automorphism group acts transitively on its vertices.. A graph is vertex-transitive if and only if its graph complement is, since the group actions are identical. Every symmetric graph without isolated vertices is vertex-transitive, and every vertex-transitive graph is regular. However, not all vertex-transitive graphs are symmetric (for example, the edges of the truncated tetrahedron), and not all regular graphs are vertex-transitive (for example, the Frucht graph and Tietze's graph). Finite examples Finite vertex-transitive graphs include the symmetric graphs (such as the Petersen graph, the Heawood graph and the vertices and edges of the Platonic solids). The finite Cayley graphs (such as cube-connected cycles) are also ve ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cop Number
In graph theory, a branch of mathematics, the cop number or copnumber of an undirected graph is the minimum number of cops that suffices to ensure a win (i.e., a capture of the robber) in a certain pursuit–evasion game on the graph. Rules In this game, one player controls the position of a given number of cops and the other player controls the position of a robber. The cops are trying to catch the robber by moving to the same position, while the robber is trying to remain uncaught. Thus, the players perform the following actions, taking turns with each other: *On the first turn of the game, the player controlling the cops places each cop on a vertex of the graph (allowing more than one cop to be placed on the same vertex). *Next, the player controlling the robber places the robber on a vertex of the graph. *On each subsequent turn, the player controlling the cops chooses a (possibly empty) subset of the cops, and moves each of these cops to adjacent vertices. The remaining cops (i ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Queue Number
In the mathematical field of graph theory, the queue number of a graph is a graph invariant defined analogously to stack number (book thickness) using first-in first-out (queue) orderings in place of last-in first-out (stack) orderings. Definition A queue layout of a given graph is defined by a total ordering of the vertices of the graph together with a partition of the edges into a number of "queues". The set of edges in each queue is required to avoid edges that are properly nested: if and are two edges in the same queue, then it should not be possible to have in the vertex ordering. The queue number of a graph is the minimum number of queues in a queue layout.. Equivalently, from a queue layout, one could process the edges in a single queue using a queue data structure, by considering the vertices in their given ordering, and when reaching a vertex, dequeueing all edges for which it is the second endpoint followed by enqueueing all edges for which it is the first en ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Book Thickness
In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings into a ''book'', a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie on this boundary line, called the ''spine'', and the edges are required to stay within a single half-plane. The book thickness of a graph is the smallest possible number of half-planes for any book embedding of the graph. Book thickness is also called pagenumber, stacknumber or fixed outerthickness. Book embeddings have also been used to define several other graph invariants including the pagewidth and book crossing number. Every graph with vertices has book thickness at most \lceil n/2\rceil, and this formula gives the exact book thickness for complete graphs. The graphs with book thickness one are the outerplanar graphs. The graphs with book thickness at most two are the subhamiltonian graphs, which are always planar; more generally, ev ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
K-edge-connected Graph
In graph theory, a connected graph is -edge-connected if it remains connected whenever fewer than edges are removed. The edge-connectivity of a graph is the largest for which the graph is -edge-connected. Edge connectivity and the enumeration of -edge-connected graphs was studied by Camille Jordan in 1869. Formal definition Let G = (V, E) be an arbitrary graph. If subgraph G' = (V, E \setminus X) is connected for all X \subseteq E where , X, < k, then ''G'' is ''k''-edge-connected. The edge connectivity of is the maximum value ''k'' such that ''G'' is ''k''-edge-connected. The smallest set ''X'' whose removal disconnects ''G'' is a in ''G''. The edge connectivity version of provi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
K-vertex-connected Graph
In graph theory, a connected graph is said to be -vertex-connected (or -connected) if it has more than vertices and remains connected whenever fewer than vertices are removed. The vertex-connectivity, or just connectivity, of a graph is the largest for which the graph is -vertex-connected. Definitions A graph (other than a complete graph) has connectivity ''k'' if ''k'' is the size of the smallest subset of vertices such that the graph becomes disconnected if you delete them. Complete graphs are not included in this version of the definition since they cannot be disconnected by deleting vertices. The complete graph with ''n'' vertices has connectivity ''n'' − 1, as implied by the first definition. An equivalent definition is that a graph with at least two vertices is ''k''-connected if, for every pair of its vertices, it is possible to find ''k'' vertex-independent paths connecting these vertices; see Menger's theorem . This definition produces the same ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Chromatic Number
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color. Vertex coloring is often used to introduce graph coloring problems, since other coloring problems can be transformed into a vertex coloring instance. For example, an edge coloring of a graph is just a vertex coloring of its line graph, and a face coloring of a plane graph is just a vertex coloring of its dual. However, non-vertex coloring problems are often stated and studied as-is. This is ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Neil Robertson (mathematician)
George Neil Robertson (born November 30, 1938) is a mathematician working mainly in topological graph theory, currently a distinguished professor emeritus at the Ohio State University. Education Robertson earned his B.Sc. from Brandon College in 1959, and his Ph.D. in 1969 at the University of Waterloo under his doctoral advisor William Tutte. Biography In 1969, Robertson joined the faculty of the Ohio State University, where he was promoted to Associate Professor in 1972 and Professor in 1984. He was a consultant with Bell Communications Research from 1984 to 1996. He has held visiting faculty positions in many institutions, most extensively at Princeton University from 1996 to 2001, and at Victoria University of Wellington, New Zealand, in 2002. He also holds an adjunct position at King Abdulaziz University in Saudi Arabia.. Research Robertson is known for his work in graph theory, and particularly for a long series of papers co-authored with Paul Seymour and published over a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
