User:HandThumb/sandbox

Gary Theodore Chartrand (born 1936) is an American-born mathematician who specializes in graph theory. 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. He has authored several books on the subject and is currently a professor emeritus of mathematics at Western Michigan University.

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. Growing up he spent much time playing sports, especially baseball, and he is a loyal fan of the Detroit Tigers. Other interests of his include movies and musical theater. He has attended over 700 performances in his lifetime. His passion has lead him to travel to New York City’s theater district numerous times, where he watched the original cast of “Wicked” perform the show in 2004. He has met composer Stephen Schwartz and corresponded with Thomas Schmancer, president of Disney Theatricals.
 Chartrand recalls doing loving English and Mathematics in junior high school and high school, and doing well in both subjects. As an undergraduate student, he initially majored in chemical engineering. He enjoyed chemistry very much, but decided to switch his major to mathematics in his junior year. Chartrand found himself behind some of his peers because of this change, but after working persistently he managed to catch up to his classmates. Gary Chartrand also became a member of the honorary mathematics society Pi Mu Epsilon in his junior year. Advisor and then department chair J. Sutherland Frame supported Chartrand’s interests in mathematics and encouraged him to pursue a graduate degree, which he did. Chartrand has said that the proof-heavy focus of his graduate classes was a challenging adjustment, and topics such as modern algebra and set theory demanded extra effort. After much determination, Chartrand gained insight into the mathematics he had studied, and became the first doctoral student of Edward Nordhaus, and the first doctoral student at Michigan State University to research graph theory. He earned his PhD in 1964 for his dissertation “Graphs and Their Associated Line-Graphs” and has worked at Western Michigan University ever since. He has advised 22 doctoral students so far on their own research in the field of graph theory. Chartrand’s work has also lead him to meet graph theorists like William Tutte, Claude Berge, Roberto Frucht, Hassler Whitney, Kazimierz Kuratowski, and Frank Harary. Chartrand worked with Frank Harary at the University of Michigan, where he spent a year as a Research Associate, and the two have published numerous papers together (along with other authors). Chartrand counts Harary as an important influence on his work in graph theory, and regards him as a role model.
 Chartrand has published several books on the topic of graph theory, many with the intention of making the topic interesting and accessible to a broad range of students. He is currently working with Ping Zhang, a frequent collaborator, and Arthur Benjamin of Harvey Mudd College on a new book, The Fascinating World of Graph Theory. Chartrand recalls his own passion in math stemmed from the understanding of its myriad applications, and with this book he and the authors hope to expose readers to the numerous uses of graph theory in resolving important questions.
 Among Gary Chartrand’s publications are papers he wrote with Paul Erdős and others on the topic of Highly Irregular Graphs. Chartrand remembers Erdős as a very kind man open to discussing all types of mathematical questions. Chartrand asked Erdős if he had ever met Albert Einstein, and Erdos responded that he had met him only once, and that they spoke about religion.
Besides his work with Erdős, Chartrand has also published numerous articles on the areas of graph theory which most interest him, which he states are “graph structures, graph colorings, distance in graphs, and domination.”

External links

• Chartrand's web page at Western Michigan University

In graph theory, a graph is irregular if for each vertex v of G the neighbors of v have distinct degrees.

History

Irregular graphs were initially characterized by Yousef Alavi, Gary Chartrand, F R K Chung, Paul Erdős, R L Graham, and Ortrud Oellerman. They were motivated to define the ‘opposite’ of a regular graph, 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. In any graph G, two vertices in G must have the same degree, so an irregular graph cannot be defined as a graph with all vertices of different degrees. One may be tempted then to define an irregular graph as having all vertices of distinct degrees except for two, but these types of graphs are also well understood and thus not interesting.

Graph theorists thus turned to the issue of local regularity. A graph is locally regular at a vertex v if all vertices adjacent to v have degree r. A graph is thus locally irregular if for each vertex v of G the neighbors of v have distinct vertices, and these graphs are thus termed highly irregular graphs.

Properties of Irregular Graphs

Some facts about highly irregular graphs outlined by Alavi, et al

If v is a vertex of maximum degree d in a highly irregular graph H, then v is adjacent to exactly one vertex of degree 1, 2, ..., d.
The largest degree in a highly irregular graph is at most half the number of vertices.
If H is a highly irregular graph with maximum degree d, one can construct a highly irregular graph of degree d+1 by taking two copies of H and adding an edge between the two vertices of degree d.

If H(n)/G(n) goes to 0 as n goes to infinity exponentially rapidly, where H(n) is the number of (non-isomorphic) highly irregular graphs with n vertices, and G(n) is the total number of graphs with n vertices.

For a graph G, there exists a highly irregular graph H containing G as an induced subgraph.

This last observation can be considered analogous to a result of Dénes_Kőnig, which states that if H is a graph with greatest degree r, then there is a graph G which is r-regular and contains H as an induced subgraph.

Applications of Irregularity

Definitions of irregularity have been important in the study of network heterogeneity, which has implications in networks found across biology, ecology, technology, and economy. There have been several graph statistics that have been suggested, many of which are based on the number of vertices in a graph and their degrees. The characterization of highly irregular graphs has also been applied to the question of heterogeneity, yet all of these fail to shed enough light on real-world situations. Efforts continue to be made to find appropriate ways to quantify network heterogeneity.