HOME
*





Highly Irregular Graph
In graph theory, a highly irregular graph is a graph in which, for every vertex, all neighbors of that vertex have distinct degrees. History Irregular graphs were initially characterized by Yousef Alavi, Gary Chartrand, Fan Chung, Paul Erdős, Ronald Graham, and Ortrud Oellermann.
Chartrand, Gary, Paul Erdos, and Ortrud R. Oellermann. "How to define an irregular graph." College Math. J 19.1 (1988): 36–42.
They were motivated to define the ‘opposite’ of a , a concept which has been thoroughly studied and well understood.


Locality and regularity

Defining an ‘irregular graph’ was not immediately obvious. In a ''k''-regular graph, all vertices have degree ''k''. ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

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]  


picture info

Graph (discrete Mathematics)
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a Set (mathematics), set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called ''Vertex (graph theory), vertices'' (also called ''nodes'' or ''points'') and each of the related pairs of vertices is called an ''edge'' (also called ''link'' or ''line''). Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges. Graphs are one of the objects of study in discrete mathematics. The edges may be directed or undirected. For example, if the vertices represent people at a party, and there is an edge between two people if they shake hands, then this graph is undirected because any person ''A'' can shake hands with a person ''B'' only if ''B'' also shakes hands with ''A''. In contrast, if an edge from a person ''A'' to a person ''B'' m ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Degree (graph Theory)
In graph theory, the degree (or valency) of a vertex of a graph is the number of edges that are incident to the vertex; in a multigraph, a loop contributes 2 to a vertex's degree, for the two ends of the edge. The degree of a vertex v is denoted \deg(v) or \deg v. The maximum degree of a graph G, denoted by \Delta(G), and the minimum degree of a graph, denoted by \delta(G), are the maximum and minimum of its vertices' degrees. In the multigraph shown on the right, the maximum degree is 5 and the minimum degree is 0. In a regular graph, every vertex has the same degree, and so we can speak of ''the'' degree of the graph. A complete graph (denoted K_n, where n is the number of vertices in the graph) is a special kind of regular graph where all vertices have the maximum possible degree, n-1. In a signed graph, the number of positive edges connected to the vertex v is called positive deg(v) and the number of connected negative edges is entitled negative deg(v). Handshaking lemma ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Yousef Alavi
Yousef Alavi (March 19, 1928 – May 21, 2013) was an Iranian born American mathematician who specialized in combinatorics and graph theory. He received his PhD from Michigan State University in 1958. He was a professor of mathematics at Western Michigan University from 1958 until his retirement in 1996; he chaired the department from 1989 to 1992. In 1987 he received the first Distinguished Service Award of the Michigan Section of the Mathematical Association of America The Mathematical Association of America (MAA) is a professional society that focuses on mathematics accessible at the undergraduate level. Members include university, college, and high school teachers; graduate and undergraduate students; pure a ... due to his 30 years of service to the MAA; at that time, the Michigan House and Senate issued a special resolution honoring him.
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Gary Chartrand
Gary Theodore Chartrand (born 1936) is an American-born mathematician who specializes in graph theory. He is known for his textbooks on introductory graph theory and for the concept of a highly irregular graph. Biography Gary Chartrand was born in 1936. He was raised in Sault Ste. Marie, Michigan and attended J. W. Sexton High School located in Lansing, Michigan. As an undergraduate student, he initially majored in chemical engineering, but switched to mathematics in his junior year, in which he also became a member of the honorary mathematics society Pi Mu Epsilon. He earned his B. S. from Michigan State University, where he majored in mathematics and minored in physical sciences and foreign languages. Michigan State University also awarded him a Master of Science and a PhD for his work in graph theory in 1964. Chartrand became the first doctoral student of Edward Nordhaus, and the first doctoral student at Michigan State University to research graph theory. His dissertation ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Fan Chung
Fan-Rong King Chung Graham (; born October 9, 1949), known professionally as Fan Chung, is a Taiwanese-born American mathematician who works mainly in the areas of spectral graph theory, extremal graph theory and random graphs, in particular in generalizing the Erdős–Rényi model for graphs with general degree distribution (including power-law graphs in the study of large information networks). Since 1998, Chung has been the Paul Erdős Professor in Combinatorics at the University of California, San Diego (UCSD). She received her doctorate from the University of Pennsylvania in 1974, under the direction of Herbert Wilf. After working at Bell Laboratories and Bellcore for nineteen years, she joined the faculty of the University of Pennsylvania as the first female tenured professor in mathematics. She serves on the editorial boards of more than a dozen international journals. Since 2003 she has been the editor-in-chief of ''Internet Mathematics''. She has been invited to give lec ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Paul Erdős
Paul Erdős ( hu, Erdős Pál ; 26 March 1913 – 20 September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in discrete mathematics, graph theory, number theory, mathematical analysis, approximation theory, set theory, and probability theory. Much of his work centered around discrete mathematics, cracking many previously unsolved problems in the field. He championed and contributed to Ramsey theory, which studies the conditions in which order necessarily appears. Overall, his work leaned towards solving previously open problems, rather than developing or exploring new areas of mathematics. Erdős published around 1,500 mathematical papers during his lifetime, a figure that remains unsurpassed. He firmly believed mathematics to be a social activity, living an itinerant lifestyle with the sole purpose of writing mathematical papers with other mathem ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Ronald Graham
Ronald Lewis Graham (October 31, 1935July 6, 2020) was an American mathematician credited by the American Mathematical Society as "one of the principal architects of the rapid development worldwide of discrete mathematics in recent years". He was president of both the American Mathematical Society and the Mathematical Association of America, and his honors included the Leroy P. Steele Prize for lifetime achievement and election to the National Academy of Sciences. After graduate study at the University of California, Berkeley, Graham worked for many years at Bell Labs and later at the University of California, San Diego. He did important work in scheduling theory, computational geometry, Ramsey theory, and quasi-randomness, and many topics in mathematics are named after him. He published six books and about 400 papers, and had nearly 200 co-authors, including many collaborative works with his wife Fan Chung and with Paul Erdős. Graham has been featured in ''Ripley's Believe ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  




Ortrud Oellermann
Ortrud R. Oellermann is a South African mathematician specializing in graph theory. She is a professor of mathematics at the University of Winnipeg. Education and career Oellermann was born in Vryheid. She earned a bachelor's degree, ''cum laude'' honours, and a master's degree at the University of Natal in 1981, 1982, and 1983 respectively, as a student of Henda Swart. She completed her Ph.D. in 1986 at Western Michigan University. Her dissertation was ''Generalized Connectivity in Graphs'' and was supervised by Gary Chartrand. Oellermann taught at the University of Durban-Westville, Western Michigan University, University of Natal, and Brandon University, before moving to Winnipeg in 1996. At Winnipeg, she was co-chair of mathematics and statistics for 2011–2013. Contributions With Gary Chartrand, Oellermann is the author of the book ''Applied and Algorithmic Graph Theory'' (McGraw Hill, 1993). She is also the author of well-cited research publications on metric dimension ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Regular Graph
In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other. A regular graph with vertices of degree is called a graph or regular graph of degree . Also, from the handshaking lemma, a regular graph contains an even number of vertices with odd degree. Regular graphs of degree at most 2 are easy to classify: a graph consists of disconnected vertices, a graph consists of disconnected edges, and a graph consists of a disjoint union of cycles and infinite chains. A graph is known as a cubic graph. A strongly regular graph is a regular graph where every adjacent pair of vertices has the same number of neighbors in common, and every non-adjacent pair of vertices has the same number of neighbors in common. The smallest graphs that are regular but not strong ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Induced Subgraph
In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset. Definition Formally, let G=(V,E) be any graph, and let S\subset V be any subset of vertices of . Then the induced subgraph G is the graph whose vertex set is S and whose edge set consists of all of the edges in E that have both endpoints in S . That is, for any two vertices u,v\in S , u and v are adjacent in G if and only if they are adjacent in G . The same definition works for undirected graphs, directed graphs, and even multigraphs. The induced subgraph G may also be called the subgraph induced in G by S , or (if context makes the choice of G unambiguous) the induced subgraph of S . Examples Important types of induced subgraphs include the following. *Induced paths are induced subgraphs that are paths. The shortest path between ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Dénes Kőnig
Dénes Kőnig (September 21, 1884 – October 19, 1944) was a Hungarian mathematician of Jewish heritage who worked in and wrote the first textbook on the field of graph theory. Biography Kőnig was born in Budapest, the son of mathematician Gyula Kőnig. In 1907, he received his doctorate Translated by Richard McCoart; with commentary by W.T. Tutte. at, and joined the faculty of the Royal Joseph University in Budapest (today Budapest University of Technology and Economics). His classes were visited by Paul Erdős, who, as a first year student, solved one of his problems. Kőnig became a full professor there in 1935. To honor his fathers' death in 1913, Kőnig and his brother György created the Gyula Kőnig prize in 1918. This prize was meant to be an endowment for young mathematicians, however was later devaluated. But the prize remained as a medal of high scientific recognition. In 1899, he published his first work while still attending High School in a journal ''Matematikai ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]