Highly irregular graph

Last updated

In graph theory, a highly irregular graph is a graph in which, for every vertex, all neighbors of that vertex have distinct degrees.

Graph theory study of graphs, which are mathematical structures used to model pairwise relations between objects

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 which are connected by edges. A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges, then called arrows, link two vertices asymmetrically; see Graph for more detailed definitions and for other variations in the types of graph that are commonly considered. Graphs are one of the prime objects of study in discrete mathematics.

Graph (discrete mathematics) mathematical structure; representation of a set of objects where some pairs of the objects are connected by links

In mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called vertices and each of the related pairs of vertices is called an edge. 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.

Degree (graph theory) number of edges incident to a given vertex in a node-link graph

In graph theory, the degree of a vertex of a graph is the number of edges incident to the vertex, and in a multigraph, loops are counted twice. The degree of a vertex is denoted or . The maximum degree of a graph G, denoted by Δ(G), and the minimum degree of a graph, denoted by δ(G), are the maximum and minimum degree of its vertices. In the multigraph on the right, the maximum degree is 5 and the minimum degree is 0. In a regular graph, all degrees are the same, and so we can speak of the degree of the graph. A complete graph is a special kind of regular graph where all vertices,p ,have the maximum degree, p-1. A complete graph is denoted with the form Kp where p is the number of vertices in the graph.

Contents

History

Irregular graphs were initially characterized by Yousef Alavi, Gary Chartrand, Fan Chung, Paul Erdős, Ronald Graham, and Ortrud Oellermann. [1] They were motivated to define the ‘opposite’ of a regular graph, a concept which has been thoroughly studied and well understood.

Yousef Alavi was an Iranian born American mathematician who specialized in combinatorics and graph theory. He received his Ph.D. 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.

Gary Chartrand American mathematician

Gary Theodore Chartrand 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.

Fan Chung mathematician

Fan-Rong King Chung Graham, 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.

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. [2]

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 degrees, and these graphs are thus termed highly irregular graphs. [1]

Properties of irregular graphs

Some facts about highly irregular graphs outlined by Alavi et al.: [3]

In 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 connecting pairs of vertices in that subset.

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. [3]

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. [4] 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. [4]

Related Research Articles

This is a glossary of graph theory terms. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by edges.

Clique (graph theory) subset of the vertices of a node-link graph that are all adjacent to each other

In the mathematical area of graph theory, a clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent; that is, its induced subgraph is complete. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science: the task of finding whether there is a clique of a given size in a graph is NP-complete, but despite this hardness result, many algorithms for finding cliques have been studied.

Extremal graph theory

Extremal graph theory is a branch of the mathematical field of graph theory. Extremal graph theory studies extremal graphs which satisfy a certain property. Extremality can be taken with respect to different graph invariants, such as order, size or girth. More abstractly, it studies how global properties of a graph influence local substructures of the graph.

Vertex (graph theory) fundamental unit of which graphs (in graph theory) are formed

In mathematics, and more specifically in graph theory, a vertex or node is the fundamental unit of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges, while a directed graph consists of a set of vertices and a set of arcs. In a diagram of a graph, a vertex is usually represented by a circle with a label, and an edge is represented by a line or arrow extending from one vertex to another.

In the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. The name line graph comes from a paper by Harary & Norman (1960) although both Whitney (1932) and Krausz (1943) used the construction before this. Other terms used for the line graph include the covering graph, the derivative, the edge-to-vertex dual, the conjugate, the representative graph, and the ϑ-obrazom, as well as the edge graph, the interchange graph, the adjoint graph, and the derived graph.

In graph theory, a clustering coefficient is a measure of the degree to which nodes in a graph tend to cluster together. Evidence suggests that in most real-world networks, and in particular social networks, nodes tend to create tightly knit groups characterised by a relatively high density of ties; this likelihood tends to be greater than the average probability of a tie randomly established between two nodes.

Wheel graph graph formed from a cycle graph by adding a new vertex adjacent to all the vertices in the cycle

In the mathematical discipline of graph theory, a wheel graph is a graph formed by connecting a single universal vertex to all vertices of a cycle. A wheel graph with n vertices can also be defined as the 1-skeleton of an (n-1)-gonal pyramid. Some authors write Wn to denote a wheel graph with n vertices ; other authors instead use Wn to denote a wheel graph with n+1 vertices, which is formed by connecting a single vertex to all vertices of a cycle of length n. In the rest of this article we use the former notation.

In graph theory, a Moore graph is a regular graph of degree d and diameter k whose number of vertices equals the upper bound

Rado graph infinite graph containing all countable graphs

In the mathematical field of graph theory, the Rado graph, Erdős–Rényi graph, or random graph is a countably infinite graph that can be constructed by choosing independently at random for each pair of its vertices whether to connect the vertices by an edge. The names of this graph honor Richard Rado, Paul Erdős, and Alfréd Rényi, mathematicians who studied it in the early 1960s; it appears even earlier in the work of Wilhelm Ackermann (1937). The Rado graph can also be constructed non-randomly, by symmetrizing the membership relation of the hereditarily finite sets, by applying the BIT predicate to the binary representations of the natural numbers, or as an infinite Paley graph that has edges connecting pairs of prime numbers congruent to 1 mod 4 that are quadratic residues modulo each other.

Erdős–Rényi model

In the mathematical field of graph theory, the Erdős–Rényi model is either of two closely related models for generating random graphs. They are named after mathematicians Paul Erdős and Alfréd Rényi, who first introduced one of the models in 1959, while Edgar Gilbert introduced the other model contemporaneously and independently of Erdős and Rényi. In the model of Erdős and Rényi, all graphs on a fixed vertex set with a fixed number of edges are equally likely; in the model introduced by Gilbert, each edge has a fixed probability of being present or absent, independently of the other edges. These models can be used in the probabilistic method to prove the existence of graphs satisfying various properties, or to provide a rigorous definition of what it means for a property to hold for almost all graphs.

In the mathematical discipline of graph theory, the Erdős–Pósa theorem, named after Paul Erdős and Lajos Pósa, states that there is a function f(k) such that for each positive integer k, every graph either contains k vertex-disjoint circuits or it has a feedback vertex set of f(k) vertices that intersects every circuit. Furthermore, f(k) = O(k log k) in the sense of Big O notation. Because of this theorem, circuits are said to have the Erdős–Pósa property.

In graph theory, the De Bruijn–Erdős theorem relates graph coloring of an infinite graph to the same problem on its finite subgraphs. It states that, when all finite subgraphs can be colored with colors, the same is true for the whole graph. The theorem was proved by Nicolaas Govert de Bruijn and Paul Erdős (1951), after whom it is named.

Degeneracy (graph theory)

In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges. The degeneracy of a graph is the smallest value of k for which it is k-degenerate. The degeneracy of a graph is a measure of how sparse it is, and is within a constant factor of other sparsity measures such as the arboricity of a graph.

The HCS clustering algorithm is an algorithm based on graph connectivity for Cluster analysis, by first representing the similarity data in a similarity graph, and afterwards finding all the highly connected subgraphs as clusters. The algorithm does not make any prior assumptions on the number of the clusters. This algorithm was published by Erez Hartuv and Ron Shamir in 1998.

Half graph

In graph theory, a branch of mathematics, a half graph is a special type of bipartite graph. These graphs are called the half graphs because they have approximately half of the edges of a complete bipartite graph on the same vertices. The name was given to these graphs by Paul Erdős and András Hajnal.

Ortrud R. Oellermann is a South African mathematician specializing in graph theory. She is a professor of mathematics at the University of Winnipeg.

References

  1. 1 2 Chartrand, Gary, Paul Erdos, and Ortrud R. Oellermann. "How to define an irregular graph." College Math. J 19.1 (1988): 36–42.
  2. ↑ Behzad, Mehdi, and Gary Chartrand. "No graph is perfect." American Mathematical Monthly (1967): 962–963.
  3. 1 2 3 4 5 6 7 Alavi, Yousef, et al. "Highly irregular graphs." Journal of graph theory 11.2 (1987): 235–249.
  4. 1 2 Estrada, Ernesto. "Quantifying network heterogeneity." Physical Review E 82.6 (2010): 066102.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.