|
Balaban 11-cage
In the mathematical field of graph theory, the Balaban 11-cage or Balaban (3,11)-cage is a 3-regular graph with 112 vertices and 168 edges named after Alexandru T. Balaban. The Balaban 11-cage is the unique (3,11)-cage. It was discovered by Balaban in 1973. The uniqueness was proved by Brendan McKay and Wendy Myrvold in 2003. The Balaban 11-cage is a Hamiltonian graph and can be constructed by excision from the Tutte 12-cage by removing a small subtree and suppressing the resulting vertices of degree two.Geoffrey Exoo & Robert Jajcay, Dynamic cage survey, Electr. J. Combin. 15 (2008) It has independence number 52, chromatic number 3, chromatic index 3, radius 6, diameter 8 and girth 11. It is also a 3- vertex-connected graph and a 3- edge-connected graph. The characteristic polynomial of the Balaban 11-cage is: :(x-3) x^ (x^2-6)^5 (x^2-2)^ (x^3-x^2-4 x+2)^2\cdot :\cdot(x^3+x^2-6 x-2) (x^4-x^3-6 x^2+4 x+4)^4 \cdot :\cdot(x^5+x^4-8 x^3-6 x^2+12 x+4)^8. The automorphism group o ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Balaban 11-cage
In the mathematical field of graph theory, the Balaban 11-cage or Balaban (3,11)-cage is a 3-regular graph with 112 vertices and 168 edges named after Alexandru T. Balaban. The Balaban 11-cage is the unique (3,11)-cage. It was discovered by Balaban in 1973. The uniqueness was proved by Brendan McKay and Wendy Myrvold in 2003. The Balaban 11-cage is a Hamiltonian graph and can be constructed by excision from the Tutte 12-cage by removing a small subtree and suppressing the resulting vertices of degree two.Geoffrey Exoo & Robert Jajcay, Dynamic cage survey, Electr. J. Combin. 15 (2008) It has independence number 52, chromatic number 3, chromatic index 3, radius 6, diameter 8 and girth 11. It is also a 3- vertex-connected graph and a 3- edge-connected graph. The characteristic polynomial of the Balaban 11-cage is: :(x-3) x^ (x^2-6)^5 (x^2-2)^ (x^3-x^2-4 x+2)^2\cdot :\cdot(x^3+x^2-6 x-2) (x^4-x^3-6 x^2+4 x+4)^4 \cdot :\cdot(x^5+x^4-8 x^3-6 x^2+12 x+4)^8. The automorphism group o ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Tutte 12-cage
In the mathematical field of graph theory, the Tutte 12-cage or Benson graph is a 3-regular graph with 126 vertices and 189 edges named after W. T. Tutte. The Tutte 12-cage is the unique (3-12)-cage . It was discovered by C. T. Benson in 1966. It has chromatic number 2 ( bipartite), chromatic index 3, girth 12 (as a 12-cage) and diameter 6. Its crossing number is 170 and has been conjectured to be the smallest cubic graph with this crossing number. Construction The Tutte 12-cage is a cubic Hamiltonian graph and can be defined by the LCF notation 7, 27, –13, –59, –35, 35, –11, 13, –53, 53, –27, 21, 57, 11, –21, –57, 59, –17sup>7. There are, up to isomorphism, precisely two generalized hexagons of order ''(2,2)'' as proved by Cohen and Tits. They are the split Cayley hexagon ''H(2)'' and its point-line dual. Clearly both of them have the same incidence graph, which is in fact isomorphic to the Tutte 12-cage. The Balaban 1 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
IEEE Computer Society
The Institute of Electrical and Electronics Engineers (IEEE) is a 501(c)(3) professional association for electronic engineering and electrical engineering (and associated disciplines) with its corporate office in New York City and its operations center in Piscataway, New Jersey. The mission of the IEEE is ''advancing technology for the benefit of humanity''. The IEEE was formed from the amalgamation of the American Institute of Electrical Engineers and the Institute of Radio Engineers in 1963. Due to its expansion of scope into so many related fields, it is simply referred to by the letters I-E-E-E (pronounced I-triple-E), except on legal business documents. , it is the world's largest association of technical professionals with more than 423,000 members in over 160 countries around the world. Its objectives are the educational and technical advancement of electrical and electronic engineering, telecommunications, computer engineering and similar disciplines. History Orig ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Petra Mutzel
Petra Mutzel is a German computer scientist, a University Professor of computer science at the University of Bonn. Her research is in the areas of algorithm engineering, graph drawing and combinatorial optimization. Education and career Mutzel earned a diploma in 1990 from the University of Augsburg, in mathematics with computer science. She then earned a doctorate in computer science from the University of Cologne in 1994 under the supervision of Michael Jünger,Faculty profile TU Dortmund, retrieved 2014-07-04. and her in 1999 from the |
Peter Eades
Peter D. Eades (born 8 January 1952) is an Australian computer scientist, an emeritus professor in the School of Information Technologies at the University of Sydney, known for his expertise in graph drawing. Eades received his bachelor's degree in mathematics from Australian National University in 1974, and his Ph.D. in mathematics from the same university in 1977 under the supervision of Jennifer Seberry. He then did postdoctoral studies at the University of Waterloo before taking an academic position at the University of Queensland, where he remained until 1991. He was a professor of computer science at the University of Newcastle from 1992 to 1999, and joined the University of Sydney faculty in 2000. As well as his faculty position at Sydney, Eades was also a distinguished researcher at NICTA.Curriculum vitae Univ. of Sydney, retr ... [...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] |
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] |
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] |
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] |
Wendy Myrvold
Wendy Joanne Myrvold is a Canadian mathematician and computer scientist known for her work on graph algorithms, planarity testing, and algorithms in enumerative combinatorics. She is a professor emeritus of computer science at the University of Victoria. Myrvold completed her Ph.D. in 1988 at the University of Waterloo. Her dissertation, ''The Ally and Adversary Reconstruction Problems'', was supervised by Charles Colbourn Charles Joseph Colbourn (born October 24, 1953) is a Canadian computer scientist and mathematician, whose research concerns graph algorithms, combinatorial designs, and their applications. From 1996 to 2001 he was the Dorothean Professor of Comput .... References External linksHome page* Canadian women mathematicians Canadian women computer scientists Canadian computer scientists Graph theorists University of Waterloo alumni University of Victoria faculty Year of birth missing (living people) Living people {{compu-bio-stub ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cubic Graph
In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs. A bicubic graph is a cubic bipartite graph. Symmetry In 1932, Ronald M. Foster began collecting examples of cubic symmetric graphs, forming the start of the Foster census.. Many well-known individual graphs are cubic and symmetric, including the utility graph, the Petersen graph, the Heawood graph, the Möbius–Kantor graph, the Pappus graph, the Desargues graph, the Nauru graph, the Coxeter graph, the Tutte–Coxeter graph, the Dyck graph, the Foster graph and the Biggs–Smith graph. W. T. Tutte classified the symmetric cubic graphs by the smallest integer number ''s'' such that each two oriented paths of length ''s'' can be mapped to each other by exactly one symmetry of the graph. He showed that ''s'' is at most 5, and provided examples of graphs with each possible ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
