|
Sousselier Graph
The Sousselier graph is, in graph theory, a hypohamiltonian graph with 16 vertices and 27 edges. It has book thickness 3 and 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. Defi ... 2. History Hypohamiltonian graphs were first studied by Sousselier in ''Problèmes plaisants et délectables'' (1963) . In 1967, Lindgren builds an infinite sequence of hypohamiltonian graphs. The graphs of this sequence all have 6''k''+10 vertices, for every integer ''k''. The same sequence of hypohamiltonian graphs is independently built by Sousselier. In 1973 Chvátal explains in a scientific paper how edges can be added to some hypohamiltonian graphs in order to build new ones of the same order, and he names Bondy as the original author of the method. As an illustration, he shows that two ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Sousselier Graph
The Sousselier graph is, in graph theory, a hypohamiltonian graph with 16 vertices and 27 edges. It has book thickness 3 and 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. Defi ... 2. History Hypohamiltonian graphs were first studied by Sousselier in ''Problèmes plaisants et délectables'' (1963) . In 1967, Lindgren builds an infinite sequence of hypohamiltonian graphs. The graphs of this sequence all have 6''k''+10 vertices, for every integer ''k''. The same sequence of hypohamiltonian graphs is independently built by Sousselier. In 1973 Chvátal explains in a scientific paper how edges can be added to some hypohamiltonian graphs in order to build new ones of the same order, and he names Bondy as the original author of the method. As an illustration, he shows that two ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are connected by '' edges'' (also called ''links'' or ''lines''). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics. Definitions Definitions in graph theory vary. The following are some of the more basic ways of defining graphs and related mathematical structures. Graph In one restricted but very common sense of the term, a graph is an ordered pair G=(V,E) comprising: * V, a set of vertices (also called nodes or points); * E \subseteq \, a set of edges (also called links or lines), which are unordered pairs of vertices (that is, an edge is associated with t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hypohamiltonian Graph
In the mathematical field of graph theory, a graph ''G'' is said to be hypohamiltonian if ''G'' itself does not have a Hamiltonian cycle but every graph formed by removing a single vertex from ''G'' is Hamiltonian. History Hypohamiltonian graphs were first studied by . cites and as additional early papers on the subject; another early work is by . sums up much of the research in this area with the following sentence: “The articles dealing with those graphs ... usually exhibit new classes of hypohamiltonian or hypotraceable graphs showing that for certain orders ''n'' such graphs indeed exist or that they possess strange and unexpected properties.” Applications Hypohamiltonian graphs arise in integer programming solutions to the traveling salesman problem: certain kinds of hypohamiltonian graphs define facets of the ''traveling salesman polytope'', a shape defined as the convex hull of the set of possible solutions to the traveling salesman problem, and these facets may ... [...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] |
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] |
American Mathematical Monthly
''The American Mathematical Monthly'' is a mathematical journal founded by Benjamin Finkel in 1894. It is published ten times each year by Taylor & Francis for the Mathematical Association of America. The ''American Mathematical Monthly'' is an expository journal intended for a wide audience of mathematicians, from undergraduate students to research professionals. Articles are chosen on the basis of their broad interest and reviewed and edited for quality of exposition as well as content. In this the ''American Mathematical Monthly'' fulfills a different role from that of typical mathematical research journals. The ''American Mathematical Monthly'' is the most widely read mathematics journal in the world according to records on JSTOR. Tables of contents with article abstracts from 1997–2010 are availablonline The MAA gives the Lester R. Ford Awards annually to "authors of articles of expository excellence" published in the ''American Mathematical Monthly''. Editors *2022– ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Václav Chvátal
Václav (Vašek) Chvátal () is a Professor Emeritus in the Department of Computer Science and Software Engineering at Concordia University in Montreal, Quebec, Canada and a Visiting Professor at Charles University in Prague. He has published extensively on topics in graph theory, combinatorics, and combinatorial optimization. Biography Chvátal was born in 1946 in Prague and educated in mathematics at Charles University in Prague, where he studied under the supervision of Zdeněk Hedrlín. He fled Czechoslovakia in 1968, three days after the Soviet invasion, and completed his Ph.D. in Mathematics at the University of Waterloo, under the supervision of Crispin St. J. A. Nash-Williams, in the fall of 1970. Subsequently, he took positions at McGill University (1971 and 1978-1986), Stanford University (1972 and 1974-1977), the Université de Montréal (1972-1974 and 1977-1978), and Rutgers University (1986-2004) before returning to Montreal for the Canada Research Chair in Combi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Canadian Mathematical Bulletin
The ''Canadian Mathematical Bulletin'' (french: Bulletin Canadien de Mathématiques) is a mathematics journal, established in 1958 and published quarterly by the Canadian Mathematical Society. The current editors-in-chief of the journal are Antonio Lei and Javad Mashreghi. The journal publishes short articles in all areas of mathematics that are of sufficient interest to the general mathematical public. Abstracting and indexing The journal is abstracted in: for the Canadian Mathematical Bulletin. * '''' * '' [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
