nach oben

2018 | Buch

Kapitel lesen Erstes Kapitel lesen

Graph Theory

Favorite Conjectures and Open Problems - 2

herausgegeben von: Ralucca Gera, Teresa W. Haynes, Stephen T. Hedetniemi

Verlag: Springer International Publishing

Buchreihe : Problem Books in Mathematics

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This second volume in a two-volume series provides an extensive collection of conjectures and open problems in graph theory. It is designed for both graduate students and established researchers in discrete mathematics who are searching for research ideas and references. Each chapter provides more than a simple collection of results on a particular topic; it captures the reader’s interest with techniques that worked and failed in attempting to solve particular conjectures. The history and origins of specific conjectures and the methods of researching them are also included throughout this volume. Students and researchers can discover how the conjectures have evolved and the various approaches that have been used in an attempt to solve them. An annotated glossary of nearly 300 graph theory parameters, 70 conjectures, and over 600 references is also included in this volume. This glossary provides an understanding of parameters beyond their definitions and enables readers to discover new ideas and new definitions in graph theory.

The editors were inspired to create this series of volumes by the popular and well-attended special sessions entitled “My Favorite Graph Theory Conjectures,” which they organized at past AMS meetings. These sessions were held at the winter AMS/MAA Joint Meeting in Boston, January 2012, the SIAM Conference on Discrete Mathematics in Halifax in June 2012, as well as the winter AMS/MAA Joint Meeting in Baltimore in January 2014, at which many of the best-known graph theorists spoke. In an effort to aid in the creation and dissemination of conjectures and open problems, which is crucial to the growth and development of this field, the editors invited these speakers, as well as other experts in graph theory, to contribute to this series.

Inhaltsverzeichnis

Frontmatter

Introduction

Abstract

This book is the second in a two-volume series on conjectures and open problems in graph theory. The primary motivation, theme, and vision of the series was expressed in the Introduction to Volume I, a slightly revised version of which we reproduce here.

Ralucca Gera, Stephen T. Hedetniemi, Teresa W. Haynes

Desert Island Conjectures

Abstract

For decades, Desert Island Discs has been a popular radio program on the BBC. Its format is for a guest to choose a selection of musical recordings that they would like to have with them if they were stranded on a desert island. In this chapter, we will unashamedly imitate that program and select some conjectures that we would like to have with us were we to be stranded on a desert island. Our selections go back about half a century, to when we were first introduced to graph theory. In the first part of this chapter, our conjectures involve drawings and embeddings of graphs on surfaces, but in the second part, we present one on connectivity.

Lowell W. Beineke

Binding Number, Cycles, and Cliques

Abstract

I discuss the binding number of a graph and Woodall’s conjecture that binding number at least 3∕2 implies a graph is pancyclic.

Wayne Goddard

A Conjecture on Laplacian Eigenvalues of Trees

Abstract

Motivated by classic tree algorithms, in 1995 we designed a bottom-up O(n) algorithm to compute the determinant of a tree’s adjacency matrix A. In 2010 an O(n) algorithm was found for constructing a diagonal matrix congruent to A + xI _n, \(x \in \mathbb {R}\), enabling one to easily count the number of eigenvalues in any interval. A variation of the algorithm allows Laplacian eigenvalues in trees to be counted. We conjecture that for any tree T of order n ≥ 2, at least half of its Laplacian eigenvalues are less than \(\bar {d} = 2 - \frac {2}{n} \), its average vertex degree.

David P. Jacobs, Vilmar Trevisan

Queens Around the World in Twenty-Five Years

Abstract

It is a truth universally acknowledged that a mathematician entering a new field must be in want of a good problem.

William D. Weakley

Reflections on a Theme of Ulam

Abstract

The annual Southeastern International Conference on Graph Theory, Combinatorics, and Computing is among the longest-running combinatorics conferences in the U.S. Launched in 1970, it was originally held in alternate years at Louisiana State University in Baton Rouge, LA and at Florida Atlantic University (FAU) in Boca Raton, FL. However, it is now held exclusively each year at FAU under the dedicated leadership of the redoubtable Fred Hoffman. (In fact, the 48th annual Conference took place in March, 2017.) Among the many attractions of this meeting, besides the marvelous climate of Florida in March, is the laid back atmosphere that permeates the meeting environment. The beach is nearby, the tennis courts are active (and in the old days, no one could defeat Ernie Cockayne and Steve Hedetniemi), and everyone who wants to give a talk can. (Of course, this policy can result in an interesting variety of presentations!)

Ron Graham

Ulam Numbers of Graphs

Abstract

Let G ₁ = (V ₁, E ₁) and G ₂ = (V ₂, E ₂) be two graphs having |V ₁| = |V ₂| and |E ₁| = |E ₂|. By an Ulam decomposition of order r we mean two partitions π ₁ = {E _1,1, E _1,2, …, E _1,r} of E ₁ and π ₂ = {E _2,1, E _2,2, …, E _2,r} of E ₂, having the properties for all 1 ≤ i ≤ r, (1) |E _1,i| = |E _2,i| and (2) the subgraph G[E _1,i] induced by E _1,i is isomorphic to the subgraph G[E _2,i] induced by E _2,i. In this note we generalize this concept, first introduced in 1979 by Chung et al. in Congr Numer 23:3–18, 1979.

Stephen T. Hedetniemi

Forbidden Trees

Abstract

This chapter deals with some of the interesting properties of graphs that do not contain one of the two trees on four vertices, P ₄ or K _1,3, as an induced subgraph, and with several conjectures that are related to forbidding these and similar trees.

David Sumner

Some of My Favourite Conjectures: Local Conditions Implying Global Cycle Properties

Abstract

Graph Theory is believed to have begun with the famous Königsberg Bridge Problem. Figure 1 shows a map of Königsberg as it appeared in the eighteenth century. The town was spanned by seven bridges passing over the river Pregel and connecting the four land masses on which Königsberg was built. The townsfolk amused themselves by taking walks through Königsberg, attempting to cross each of the seven bridges exactly once. In 1736 Euler put an end to their speculation that such a walk did not exist by giving a rigorous argument which proved their conjecture. Motivated by this problem, a graph is called eulerian if it has a closed walk that traverses each edge exactly once. It is well known that a connected graph is eulerian if and only if the degree of each vertex is even. The eulerian problem for connected graphs is thus easily solved by checking whether the degree of each vertex is even. The vertex analogue of eulerian graphs are the Hamiltonian graphs. These are graphs that have a cycle that passes through each vertex exactly once and are named after Sir William Rowan Hamilton who devised the Icosian Game for two players. One of the problems in the game required the first player to select a path of five vertices on the dodecahedron. The second player had to extend this path to a cycle that contained all 20 points of the dodecahedron. If a graph has a cycle that contains all its vertices such a cycle is called a Hamiltonian cycle. In contrast to the eulerian problem, the Hamilton cycle problem, i.e., the problem of determining whether a given graph has a Hamiltonian cycle, has no known simple solution. As a result many sufficient conditions for hamiltonicity have been established. In this chapter we will describe problems and conjectures that have their roots in the Hamilton cycle problem.

Ortrud R. Oellermann

The Path Partition Conjecture

Abstract

The Path Partition Conjecture (PPC) states that if G is any graph and (a, b) any pair of positive integers such that G has no path with more than a + b vertices, then there exists a partition (A, B) of the vertex set of G such that A has no path with more than a vertices, and B has no path with more than b vertices. We present a brief history of the PPC, discuss its relation to other conjectures and examine results supporting the PPC that have appeared in the literature since its first formulation in 1981. We conclude with a few related open problems.

Marietjie Frick, Jean E. Dunbar

To the Moon and Beyond

Abstract

Are there nontrivial integer solutions to the equation x ⁿ + y ⁿ = z ⁿ for any integer n ≥ 2? How about for n > 2? Wait a minute! Is this a chapter about Fermat’s Last Theorem or about Graph Coloring? From one point of view, theorems such as The Four Color Theorem and Fermat’s Last Theorem are no more important than countless other problems in chromatic graph theory or in diophantine equations, respectively, and yet both problems are pervasive in science and culture.

Ellen Gethner

My Favorite Domination Game Conjectures

Abstract

The domination game belongs to the growing family of competitive optimization graph games, and describes a process in which two players, Dominator and Staller, with conflicting goals collaboratively produce a dominating set in an underlying host graph. The players take turns choosing a vertex from the graph, where each vertex chosen must dominate at least one vertex not dominated by the set of vertices previously chosen. The game ends when there are no more moves available. The players’ goals are completely antithetical: while Dominator wants to minimize the size of a dominating set, Staller wants to maximize it. In this chapter, we discuss some of the conjectures on domination-type game parameters.

Michael A. Henning

A De Bruijn–Erdős Theorem in Graphs?

Abstract

A set of n points in the Euclidean plane determines at least n distinct lines unless these n points are collinear. In 2006, Chen and Chvátal asked whether the same statement holds true in general metric spaces, where the line determined by points x and y is defined as the set consisting of x, y, and all points z such that one of the three points x, y, z lies between the other two. The conjecture that it does hold true remains unresolved even in the special case where the metric space arises from a connected undirected graph with unit lengths assigned to edges. We trace its curriculum vitae and point out twenty-nine related open problems plus three additional conjectures.

Vašek Chvátal

An Annotated Glossary of Graph Theory Parameters, with Conjectures

Abstract

This glossary contains an annotated listing of some 300 parameters of graphs, together with their definitions, and, for most of these, a reference to the authors who introduced them. Let G = (V, E) be an undirected graph having order n = |V | vertices and size m = |E| edges. Two graphs G and H are isomorphic, denoted G ≃ H, if there exists a bijection ϕ : V (G) → V (H) such that two vertices u and v are adjacent in G if and only if the two vertices ϕ(u) and ϕ(v) are adjacent in H. For the purposes of this paper, we shall say that a parameter of a graph G is any integer-valued function \(f: \mathcal {G} \rightarrow \mathcal {Z}\) from the class of all finite graphs \(\mathcal {G}\) to the integers \(\mathcal {Z}\), such that for any two graphs G and H, if G is isomorphic to H then f(G) = f(H). This glossary also contains a listing of some 70 conjectures related to these parameters, more than 26 new parameters and open problem areas for study, and some 600 references to papers in which these parameters were introduced and then studied.

Ralucca Gera, Teresa W. Haynes, Stephen T. Hedetniemi, Michael A. Henning

Correction to: A De Bruijn-Erdős Theorem in Graphs?

Vašek Chvátal

Titel: Graph Theory
herausgegeben von: Ralucca Gera
Teresa W. Haynes
Stephen T. Hedetniemi
Verlag: Springer International Publishing
Electronic ISBN: 978-3-319-97686-0
Print ISBN: 978-3-319-97684-6
DOI: https://doi.org/10.1007/978-3-319-97686-0

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

Introduction

Desert Island Conjectures

Binding Number, Cycles, and Cliques

A Conjecture on Laplacian Eigenvalues of Trees

Queens Around the World in Twenty-Five Years

Reflections on a Theme of Ulam

Ulam Numbers of Graphs

Forbidden Trees

Some of My Favourite Conjectures: Local Conditions Implying Global Cycle Properties

The Path Partition Conjecture

To the Moon and Beyond

My Favorite Domination Game Conjectures

A De Bruijn–Erdős Theorem in Graphs?

An Annotated Glossary of Graph Theory Parameters, with Conjectures

Correction to: A De Bruijn-Erdős Theorem in Graphs?

Premium Partner