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.

1 Introduction

Keeping with the theme of this series of monographs, which is to provide extensive discussions of favorite conjectures and open problems in graph theory, in this chapter we present an annotated glossary of graph theory parameters along with conjectures involving many of them. We also list several suggested new parameters and open problems. Although this chapter deviates from the “story-telling style” adopted in the other chapters, we hope that this glossary with its conjectures and open problems serves as a useful tool for researchers, fitting in its own way within the theme of this series.

Let G = (V, E) be a finite undirected graph with vertex set V = {v ₁, v ₂, …, v _n} of order n = |V |, and edge set E with size m = |E|, consisting of unordered pairs of distinct vertices in V . By a partition of the vertex set V  we mean a family π = {V ₁, V ₂, …, V _k} of pairwise disjoint sets whose union equals V , that is, for all 1 ≤ i < j ≤ k, V _i ∩ V _j = ∅ and $\displaystyle {\bigcup \limits _{i=1}^k V_i = V}$; for such a partition π, we will say that π has order k. 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. Identifying when two graphs are isomorphic is both practical and theoretically interesting, while the decision problem is hard to categorize [28, 501, 505, 538]. A parameter of a graph G is a numerical value (usually a non-negative integer) that can be associated with any graph such that whenever two graphs are isomorphic, they have the same associated parameter value. A finite set $\mathcal {I}$ of parameters is said to be complete if whenever two graphs have the same values for every parameter in the set $\mathcal {I}$, then the two graphs are isomorphic. We know of no finite complete set of parameters for the class of all finite, undirected graphs. Indeed, one could easily conjecture that a finite complete set of parameters does not exist for the family of all graphs.

However, complete sets of parameters do exist for some limited families of graphs. For example, the one parameter n, the order of a graph, is a complete set of parameters for the family of all complete graphs K _n, the family of paths P _n, and the family of cycles C _n. The two parameters {n, m}, the order and the size of a graph, form a complete set for the family of all graphs of order n ≤ 3, that is, the value of these two parameters uniquely identifies any graph of order n ≤ 3. It seems likely, therefore, that complete sets of parameters can be discovered for various families of graphs. But if complete sets of parameters for limited families of graphs exist, then from what list of parameters can they be chosen?

This brings us to the first motivation for presenting a glossary of more than 300 parameters of graphs. From this listing, complete sets of parameters for limited families of graphs can be chosen.

A second motivation for creating this glossary of parameters is the study of graphical parameters themselves. What types of parameters have been defined and studied? Indeed, what other types of parameters have not been defined? Merely reading through this listing of parameters and understanding how they are defined will surely suggest even more parameters that can be studied.

A third motivation for creating this glossary has to do with results of the form: a(G) + b(G) ≤ n + c, or a(G) + b(G) ≥ n + c, where a(G) and b(G) are two parameters, n is the order of a graph G, and c is some, usually small, constant. In 1969, Geller and Hedetniemi [282] showed that for many pairs of parameters, inequalities like these exist, provided that the parameters are well-behaved under either of the following two operations: (1) identifying two non-adjacent vertices u and v in a graph G, called an elementary homomorphism, where Gε denotes the resulting graph, or (2) contracting two adjacent vertices u and v to a single vertex, called an elementary contraction, where Gθ denotes the resulting graph. By well-behaved we mean that the value of a parameter does not change by more than, say, 1; for example, if for any graph G, a(G) ≥ a(Gε) ± 1, or a(G) ≤ a(Gθ) ± 1. Often one can prove that such inequalities as a(G) + b(G) ≤ n + c or a(G) + b(G) ≥ n + c exist if one of the parameters remains unchanged while the second parameter changes by at most 1 under either of these two elementary operations. The question then is: for which pairs of parameters are such theorems possible? All that remains is to study how any of the following parameters can change under either of these two elementary operations.

A fourth motivation for creating this listing of parameters is to provide a partial answer to the general question: has a proposed new parameter already been defined? Or, has a parameter similar to a proposed parameter been defined?

A fifth, and final, motivation for creating this glossary is simply to have in one place, a reasonably comprehensive list of most of the generally recognized graph parameters, together with their definitions and a couple of references where more information about them can be found. Of course, it is recommended that one should consult a good search engine, like MathSciNet or GoogleScholar, in order to thoroughly search what is known about any of these parameters. This listing of parameters is not intended to be complete. While it may be reasonably comprehensive, the number of graph theory parameters that have been studied in the literature is much greater than the number presented here. We apologize in advance if we have omitted anyone’s favorite parameters.

One might well say that many of the graph parameters that have appeared in the literature are obscure and uninteresting. This is, of course, always a matter of personal choice. But it is too easy to make small changes in any of these definitions and thereby create a seemingly “new” parameter. Indeed, one of the criticisms of graph theory is that it has too many uninteresting parameters. One should always ask, is this “new” parameter worth studying? Is it interesting? What is the motivation for studying this new parameter? Is there some real-world application for this parameter? Is there some theoretical justification for studying it? Is it related in some interesting or important ways to existing parameters? Does this parameter help us understand better some other parameters? Just because it is “new” doesn’t mean that it is worth studying.

Thus, having a glossary of parameters provides both a reference tool for researchers and a source for open problems. In keeping with the theme of conjectures and open problems, following our glossary of parameters, we present a sample of some 70 conjectures involving them.

This glossary is certainly not the first of its kind. A discussion of many of these parameters can be found in the book Handbook of Graph Theory, Second Edition edited by Gross et al. [314], the two books Fundamentals of Domination in Graphs, [361] and Domination in Graphs, Advanced Topics [360] written and edited by Haynes, Hedetniemi and Slater, and the two books on graph coloring, Chromatic Graph Theory by Chartrand and Zhang [118], and Graph Coloring Problems by Jensen and Toft [434].

Along the direction we are taking by listing conjectures in this glossary, similar work has been conducted since 1968 by Vizing [627], Gallian’s survey of conjectures in 1989 [277], Bollobás in 2004 [60], Broersma et al. in 2012 [85], Bonato and Nowakoski in 2012 [65], and more recently by Bondy in 2014 [66]. While still a survey of conjectures, in 2010 Aouchiche and Hansen [18] wrote an expository work of conjectures in spectral graph theory conjectured by computers. In addition, lists of open problems and conjectures can be found on West’s homepage http://faculty.math.illinois.edu/~west/openp/ and the Graffiti website http://cms.dt.uh.edu/faculty/delavinae/research/wowII maintained by DeLaviña.

This glossary, however, differs in several important respects from existing glossaries and surveys. First, it is by far the most comprehensive in listing fairly well-studied graph theory parameters. Second, it is more than a listing of definitions of parameters in that it provides historical information about the origins and authors of these parameters. Third, more than a glossary, we provide annotations to many of these parameters. And fourth, we provide an extensive listing of conjectures about many of these parameters, which provides depth to simple definitions, as well as a collection of some two dozen new parameters and problems to study. In addition, this glossary provides an overview of the nature of graph theory parameters, with an eye toward the creation of new ideas in graph theory. The remainder of this glossary contains some 300 graph parameters, some 70 conjectures, and around 600 references.

2 Categories of Parameters of Graphs

In this section we discuss the mathematical nature of different types of parameters of graphs. A quick overview of these parameters shows that they naturally fall into a few general categories, the most common being the following:

• 1. Basic structural characteristics of a graph, like the order (number of vertices), the size (number of edges), the degrees of the vertices, the lengths of shortest paths between pairs of vertices (geodesics), the maximum length of a path (detour number), the minimum length of a chordless cycle (girth), the maximum length of a cycle (circumference), or the maximum order of a complete subgraph (clique number).

• 2. The minimum or maximum cardinality of a set of vertices or edges, and in a few cases a set of vertices and edges, having some given property $\mathcal {P}$. If the property $\mathcal {P}$ in question is hereditary, meaning that every subset of a set of this type, called a $\mathcal {P}$-set, is also a $\mathcal {P}$-set, then one is generally interested in sets of maximum cardinality. A common example of a hereditary property is that a set is independent, meaning no two vertices in the set are adjacent. But there is also interest in finding maximal $\mathcal {P}$-sets having minimum cardinality. Similarly, some properties $\mathcal {P}$ are super-hereditary, meaning that every superset of a $\mathcal {P}$-set is also a $\mathcal {P}$-set. A common example of a super-hereditary property is that of being a dominating set, meaning that every vertex not in the set is adjacent to at least one vertex in the set. In this case, one is interested in finding $\mathcal {P}$-sets having minimum cardinality, or minimal $\mathcal {P}$-sets of maximum cardinality.

• 3. The minimum number of vertices or edges whose removal results in a graph having some property $\mathcal {P}$, such as being disconnected, planar or bipartite, or the minimum number of vertices or edges which added to a graph results in a graph having some property $\mathcal {P}$.

• 4. The minimum or maximum order k of a partition π = {V ₁, V ₂, …, V _k} of the vertex set V , or π = {E ₁, E ₂, …, E _k} of the edge set E, such that each set V _i or E _j of the partition has some property $\mathcal {P}$. Most commonly these include a wide variety of chromatic numbers. Occasionally, a condition is placed on pairs V _i, V _j of sets, for example, that the subgraph G[V _i ∪ V _j] induced by two independent sets V _i and V _j is acyclic, these being called acyclic colorings. Again, if the property $\mathcal {P}$ is hereditary, e.g. being an independent set, then one is interested in minimum order partitions, as in the chromatic number, but if the property is super-hereditary, as is a dominating set, then one is interested in maximum order partitions, like the domatic number.

• 5. An optimal linear arrangement of the vertices or edges of a graph which minimizes or maximizes some number, as in the bandwidth of a graph, or in the bipartite crossing number.

• 6. The dimension of a certain type of vector space associated a graph, such as the rank of the adjacency matrix, incidence matrix, neighborhood matrix or the Laplacian matrix, that is, the dimension of the row space of a matrix associated with a graph.

• 7. The amount of time, or steps, necessary to accomplish some objective in a connected graph, such as broadcasting, that is, disseminating a message from one vertex in a graph to all other vertices, or in pebbling, whereby you must move pebbles in a sequence of pebbling moves so that any vertex can receive a pebble.

3 Parameters of Graphs

Before we proceed with our compendium of parameters, we need to define a few basic terms, which are used in the definitions in the following subsections.

Let G = (V, E) be a graph with vertex set V = {v ₁, v ₂, …, v _n}. The open neighborhood of a vertex v ∈ V  is the set N(v) = {u | uv ∈ E} of vertices u that are adjacent to v; these vertices are called neighbors of v. The degree of a vertex v is deg(v) = |N(v)|. The closed neighborhood of a vertex v is the set N[v] = N(v) ∪{v}. A vertex v with deg(v) = 0 is called an isolated vertex, and a vertex v with deg(v) = 1 is called a leaf.

The open neighborhood of a set S ⊆ V  of vertices is the set N(S) =⋃_{v ∈ S} N(v), and the closed neighborhood of S is the set N[S] =⋃_{v ∈ S} N[v].

A walk in a graph G from a vertex u to a vertex v is an alternating sequence of vertices u _i and edges e _i of the form W : u = u ₀, e ₁, u ₁, e ₂, u ₂, …, u _k−1, e _k, u _k = v, where for 1 ≤ i ≤ k, e _i = u _i−1 u _i. A walk W containing no repeated edges, i.e. for 1 ≤ i < j ≤ k, e _i ≠ e _j, is called a trail. A walk W containing no repeated vertices is called a path. A cycle is a path whose first and last vertices are the same. A chord is an edge between two nonconsecutive vertices of a cycle. The length of a walk equals the number of edges in the walk. The distance d(u, v) between two vertices u and v, in a connected graph G, equals the minimum length of a path from u to v. A shortest, or minimum length, path between two vertices u and v is called a u − v geodesic; a v-geodesic is any shortest path from v to another vertex; a geodesic is any shortest path in a graph.

A graph G is connected if there is a path between every pair of vertices of G. A component of a graph is a maximal connected subgraph. A vertex v ∈ V  is a cutvertex if the graph G − v obtained by deleting v and all edges containing v has more components than G. An edge e = uv is a bridge if the graph G − e obtained by deleting e has more components than G.

A graph G of order n is called k-vertex-connected (or simply, k-connected) if n ≥ k + 1 and the deletion of any k − 1 or fewer vertices leaves a connected graph.

If G = (V, E) and S ⊆ V , then the subgraph of G induced by S is the graph G[S], whose vertex set is S and whose edges are all the edges in E both of whose vertices are in S. A subgraph G′ = (V ′, E′) of a graph G is called complete if for every u, v ∈ V ′, uv ∈ E′, that is every pair of vertices in G′ are adjacent.

Let F be an arbitrary graph. A graph G is said to be F-free if G does not contain F as an induced subgraph. A graph is bipartite if its vertex set V (G) can be partitioned into two sets X and Y  such that every edge in G joins a vertex in X and a vertex in Y ; it is K ₃-free.

3.1 Basic Numbers

In this subsection we list the most basic numbers that are used in defining the parameters in the following subsections.

• 1. order n = |V |, number of vertices.

• 2. size m = |E|, number of edges.

• 3. minimum degree δ(G) = min{deg(u) : u ∈ V }, minimum degree of a vertex in G.

• 4. maximum degree Δ(G) = max{deg(u) : u ∈ V }, maximum degree of a vertex in G.

• 5. degree sequence of a graph, d ₁ ≥ d ₂ ≥… ≥ d _n, where d _i = deg(v _i) equals the degree of vertex v _i.

• 6. average degree of a graph, ${\frac {\sum _{v \in V} deg(v)}{n}} = \frac {2m}{n}$.

3.2 Connectivity and Subgraph Numbers

In this subsection we present parameters related to connectivity in graphs.

• 1. binding number bind(G), min{|N(X)|∕|X| : ∅ ≠ X ⊆ V (G) and N(X) ≠ V (G)}, defined by Katerinis and Woodall [445]. See also Lyle and Goddard [492], and Nam [511].

• 2. blocks bl(G), number of blocks in G. A block of a graph G is a maximal nonseparable subgraph of G, that is, a maximal subgraph having no cutvertices.

• 3. bridges br(G), number of bridges in G.

• 4. circumference cir(G), maximum length or order of a cycle in G.

• 5. induced circumference, maximum length of an induced cycle in G, or equivalently, maximum length of a chordless cycle in G.

• 6. clique number ω(G), maximum order of a complete subgraph of G.

• 7. components c(G), number of maximal connected subgraphs.

• 8. vertex connectivity κ(G), minimum number of vertices in a cutset. A vertex cutset is a set S ⊂ V  in a connected graph whose removal results in a graph which is either not connected or consists of a single vertex. A graph is said to be k-connected if κ(G) = k.

• 9. upper vertex connectivity κ ⁺(G), maximum number of vertices in a minimal vertex cutset.

• 10. edge connectivity λ(G), minimum number of edges in a cutset. An edge cutset is a set S ⊆ E in a connected graph whose removal results in a graph which is not connected. We assume that λ(K ₁) = 0.

• 11. upper edge connectivity λ ⁺(G), maximum number of edges in a minimal edge cutset.

• 12. cutvertices cut(G), number of cutvertices in G.

• 13. cycle number cycle(v), number of distinct cycles containing vertex v.

• 14. girth(G), minimum length of a cycle in G.

• 15. intersection number Ω(G). Let $\mathcal {F} = \{S_1, S_2, \ldots , S_k\}$ be a family of subsets of a set S. The intersection graph of $\mathcal {F}$ is the graph $G(\mathcal {F}) = (\mathcal {F}, E(\mathcal {F}))$, where two vertices S _i and S _j are adjacent in $G(\mathcal {F})$ if and only if S _i ∩ S _j ≠ ∅. The intersection number Ω(G) equals the minimum number of elements in a set S such that G is isomorphic to an intersection graph $G(\mathcal {F})$ on some family $\mathcal {F}$ of subsets of S; introduced by Erdös, Goodman, and Pósa in 1966 [226]; see also Harary [337] and [338].

• 16. edge clique cover number θ _cc(G), minimum order k of an edge clique cover, that is, a set $\mathcal {E} = \{C_1, C_2, \ldots , C_k\}$ such that (1) for 1 ≤ i ≤ k, C _i is a complete subgraph of G, and (2) for every edge uv ∈ E(G), there exists a j, 1 ≤ j ≤ k, such that uv ∈ C _j. This number equals the intersection number Ω(G), defined above; cf. Erdös, Goodman and Pósa in 1966 [226] and Harary [337].

  Theorem 1 For any graph G, Ω(G) = θ _cc(G).

• 17. toughness t(G), maximum value of t for which G is t-tough. A graph G is called t-tough if each subset S ⊆ V  with c(G − S) > 1 satisfies |S|∕c(G − S) ≥ t; defined by Chvátal in 1973 [156]. We refer the reader to the survey by Bauer [37] and also the chapter on toughness and related conjectures by Lesniak [481] in Volume 1 of this series [287].

3.3 Degree and Distance Numbers

This subsection contains the definitions of parameters which are defined in terms of the degrees of the vertices in a graph or the distances d(u, v) between vertices in a graph.

• 1. convex number cvx(G). For two vertices u, v ∈ V , let I(u, v) denote the set of all vertices lying on a u-v geodesic in G. For a set S, let I(S) = ∪_{u,v ∈ S} I(u, v). A set S is convex if I(S) = S. The convex number cvx(G) is the maximum cardinality of a proper convex set of G; introduced by Chartrand and Zhang in 1999 [115].

• 2. detour length τ′(G),¹ maximum length of a path in G, and detour number τ(G), maximum number of vertices in a path in G; introduced by Kapoor, Kronk and Lick in 1968 [442]. See also Broere et al. [83].

• 3. induced detour number idn(G), maximum length of an induced path in G; introduced by Buckley and Harary in 1988 [87].

• 4. detour number dn(G). For two vertices u, v ∈ V , the detour distance D(u, v) is the length of a longest u − v path in G. A u − v path of length D(u, v) is called a u − v detour. The closed detour interval ID[u, v] consists of u, v, and all vertices in some u − v detour in G. For S ⊆ V , ID[S] =⋃_{u,v ∈ S} ID[u, v]. A set S of vertices is a detour set if ID[S] = V , and the detour number dn(G) is the minimum cardinality of a detour set in G; cf. Chartrand et al. [128].

• 5. diameter, diam(G), maximum length of a geodesic in G, or equivalently, diam(G) = max{ecc(v) : v ∈ V }.

• 6. eccentricity ecc(v), maximum length d(v, w) of a v-geodesic, or equivalently, ecc(v) = max{d(v, w) : w ∈ V }.

• 7. geodetic number gn(G). The closed interval I[u, v] consists of vertices u and v and all vertices that lie on some u − v geodesic in G. For a set S ⊆ V , let I[S] =⋃_{u,v ∈ S} I[u, v]. A set S of vertices is a geodetic set if I[S] = V , and the minimum cardinality of a geodetic set is the geodetic number gn(G); introduced by Harary et al. [347]; see also Chartrand et al. [127] and Chartrand et al. [130].

• 8. Hamiltonian number h(G). Let c = v ₁, v ₂, …, v _n, v _n+1 = v ₁ be a cyclic ordering of the vertices of a graph G. Let $d(c) = \sum _{i=1}^n d(v_i, v_{i+1})$. The Hamiltonian number h(G) = min{d(c) : c a cyclic ordering of V }; introduced by Chartrand, Thomas, Saenpholphat, and Zhang in 2004 [131].

• 9. upper Hamiltonian number h ⁺(G) = max{d(c) : c a cyclic ordering of V }; introduced by Chartrand et al. [131].

• 10. Hamiltonian completion number hc(G), minimum number of edges not in E(G), which when added to G create a graph G′ having a Hamiltonian cycle, defined by Goodman and Hedetniemi in 1974 [309] and later expanded on by Goodman et al. in 1975 [310] and by Slater et al. in 1976 [590].

• 11. Harary index.

  $$\displaystyle \begin{aligned}H(G) = \sum_{u,v \in V} d(u, v)^{-1}\end{aligned}$$

  Introduced independently in 1993 by Plavšić et al. [523] and Ivanciuc et al.[431].

• 12. Hosoya index. One plus the number of matchings in a graph G, or equivalently, one plus the number of independent sets of edges, including the empty set; introduced by Hosoya in 1971 [423], used in the study of organic compounds, shown to be positively correlated with the boiling points of alkane isomers; also called the Z index.

• 13. weak hub-integrity WHI(G) = min{|S| + m _e(G − S)}, where S is a hub set and m _e(G − S) denotes the number of edges in a largest component of G − S; introduced by Mahde and Mathad in 2017 [494].

• 14. periphery per(G), number of vertices v with ecc(v) = diam(G). The periphery of a graph refers to either the set of all vertices having eccentricity equal to diam(G) or the subgraph induced by this set of vertices.

• 15. radius rad(G), minimum eccentricity of a vertex in G, i.e. rad(G) = min{ecc(v) : v ∈ V }. The center of a graph C(G) refers either to the set of vertices having minimum eccentricity or the subgraph induced by this set of vertices. A vertex v ∈ C(G) is called a central vertex.

• 16. status s(v) =∑_{u ∈ V} d(u, v). The median M(G) of a graph G equals the set of vertices having minimum status, or the subgraph induced by this set of vertices, defined by Harary in 1959 [336], and by Buckley and Harary in 1990 [88].

• 17. average distance $\mu (G) = \frac {1}{n(n-1)}\sigma (G)$ defined by Dankelmann in 1997 [181], where

  $$\displaystyle \begin{aligned}\sigma(G) = \sum_{u,v \in V} d(u, v)\end{aligned}$$

  is the Weiner index of G ; see below in this subsection for the definition of Weiner index.

• 18. rank r(G), the rank of the adjacency matrix A(G) of a graph G, that is, the dimension of the vector space spanned by either the columns or the rows of the adjacency matrix A(G). Let r′(G) denote the rank of the closed neighborhood matrix N(G) = A(G) + I; as discussed by Hedetniemi, Jacobs and Laskar in [386].

• 19. minimum rank mr(G), minimum rank of any generalized matrix of G. A generalized adjacency matrix of an adjacency matrix A(G) is any matrix of real numbers with the same pattern of non-zeroes as that of A(G); cf. Fallat and Hogben [240], who show that (1) mr(G) ≤ n − 1, (2) for connected G, mr(G) = 1 if and only if G = K _n, (3) mr(P _n) = n − 1, and (4) mr(C _n) = n − 2.

• 20. orthogonal rank ε(G). An orthogonal representation of a graph G is function $\phi : V \rightarrow \mathcal {C}$ from V  to the non-zero vectors of some vector space $\mathcal {C}$, such that for every uv ∈ E, ϕ(u) is orthogonal to ϕ(v). The orthogonality graph of ϕ is the graph ϕ(G) = (ϕ(V ), E(ϕ)), where ϕ(u) is adjacent to ϕ(v) if and only if ϕ(u) and ϕ(v) are orthogonal. The orthogonal rank ε(G) equals the smallest integer c such that G has an orthogonal representation in the vector space $\mathcal {C}^c.$ Let ε ₁(G) equal the smallest integer c such that G has an orthogonal representation in the vector space $\mathcal {C}^c$, such that every vector ϕ(v) has modulus one. Let χ(G) denote the chromatic number of a graph G. In [96] Cameron et al. show that for every graph G,

  $$\displaystyle \begin{aligned}\omega(G) \leq \varepsilon(G) \leq \varepsilon_1(G) \leq \chi(G).\end{aligned}$$

• 21. Randić connectivity index.

  $$\displaystyle \begin{aligned}R(G) = \sum_{uv \in E} (deg(u)deg(v))^{-1/2}.\end{aligned}$$

  Introduced by Randić in 1975 [535].

• 22. metric dimension dim(G). Let S = {v ₁, v ₂, …, v _k} be an ordered set of k vertices in a graph G = (V, E), and let w ∈ V  be an arbitrary vertex. The metric representation of w with respect to the set S is the k-vector

  $$\displaystyle \begin{aligned}r(w|S) = (d(w, v_1), d(w, v_2), \ldots, d(w, v_k)).\end{aligned}$$

  A set S is said to be a resolving set for G if distinct vertices in V  have distinct metric representations with respect to S. The minimum cardinality of a resolving set for G is called its metric dimension and is denoted dim(G).

  This concept was introduced by Slater in 1975 [584], who called the metric dimension the location number loc(G). This concept was independently introduced by Harary and Melter [343] in 1976, who used the term metric dimension.

• 23. upper metric dimension dim ⁺(G). A resolving set S for a graph G is said to be minimal if no proper subset of S is a resolving set for G. The maximum cardinality of a minimal resolving set for a graph G is called the upper metric dimension of G and is denoted dim ⁺(G); introduced by Chartrand, Poisson, and Zhang in 2000 [125], see also Chartrand and Zhang [117].

• 24. total influence number η _t(G). Given a set S ⊆ V , and a vertex v ∈ S, the total influence of v is $\eta _t(v) = \sum _{u \in V - S} \frac {1}{2^{d(u,v)}}$. The total influence of set S is η _t(S) =∑_{v ∈ S} η _t(v). The total influence of a graph G is η _t(G) = max _S⊆V{η _t(S)}; defined by Daugherty, Lyle and Laskar in 2005 [183]; cf. also Aytac and Kartal [27].

• 25. traceable number t(G). Let l = v ₁, v ₂, …, v _n be a linear ordering of the vertices of a graph G. Let $d(l) = \sum _{i=1}^{n-1} d(v_i, v_{i+1})$. The traceable number t(G) = min{d(l) : l a linear ordering of V }; introduced by Saenpholphat, Okamoto, and Zhang in 2006 [550]. The upper traceable number t ⁺(G) can also be defined as t ⁺(G) = max{d(l) : l is a linear ordering of V }. The authors also define the traceable number of a vertex v, as t(v) = min{d(l) : l is a linear ordering of V  in which v ₁ = v}. Thus, the traceable center TC(G) of G can be said to consist of the set of vertices having minimum t(v), or the subgraph induced by this set of vertices; this does not appear to have been studied.

• 26. trail number tr(G), maximum length of a trail in G; cf. Bollobás and Harary [61], who determine tr(G) over all graphs of order n and size m. Note that the trail number of a graph G equals its maximum m = |E| if and only if G has at most two vertices of odd degree, that is, G has an Eulerian walk.

• 27. Wiener index.

  $$\displaystyle \begin{aligned}\sigma(G) = \sum_{u,v \in V} d(u, v)\end{aligned}$$

  Introduced by Wiener in 1947 [638], it is the oldest topological index of the graph of a chemical compound related to molecular branching. Also studied graph theoretically by Harary as gross status [336], by Entringer, Jackson and Snyder as distance [222] and by Šoltés as the transmission number [594].

• 28. first Zagreb index, sum of the squares of the vertex degrees,

  $$\displaystyle \begin{aligned}M_1(G) = \sum_{v \in V} deg(v)^2\end{aligned}$$

  Introduced by Gutman and Trinajstić in 1972 [319]; cf. Zhou and Gutman [659].

• 29. second Zagreb index, sum of the products of the vertex degrees of adjacent vertices,

  $$\displaystyle \begin{aligned}M_2(G) = \sum_{uv \in E} deg(u)deg(v)\end{aligned}$$

  Introduced by Gutman and Trinajstić in 1972 [319]; cf. Došic et al. [203].

• 30. modified Zagreb indices. First modified Zagreb index:

  $$\displaystyle \begin{aligned}\sum_{v \in V} (deg(v)^2)^{-1}.\end{aligned}$$

  Second modified Zagreb index:

  $$\displaystyle \begin{aligned}\sum_{uv \in E} (deg(u)deg(v))^{-1}.\end{aligned}$$

  Introduced by Nicolić et al. [515].

3.4 Bandwidth and other Labeling Numbers

All of the parameters in this subsection consider proper numberings of a graph G of order n, that is, is a bijection f : V →{1, 2, …, n}, or a labeling of the vertices of G with distinct integers from 1 to n. The parameters are defined in terms of a minimum or maximum of some objective function over all possible proper numberings.

• 1. bandsize bs(G). For a proper numbering f, let bs _f(G) = |{|f(u) − f(v)| : uv ∈ E}| that is, the number of distinct differences |f(u) − f(v)| over all edges uv ∈ E. The bandsize bs(G) = min{bs _f(G) : f is a proper numbering of G}; introduced by Heinrich and Hell in 1987 [401] and Erdös, Hell and Winkler in 1989 [229].

• 2. bandwidth B(G). For a proper numbering f, B _f(G) = max{|f(u) − f(v)| : uv ∈ E}. The bandwidth B(G) = min{B _f(G) : f is a proper numbering of G}; introduced by Harper in 1964 [349]. See surveys by Chinn et al. in 1982 [152] and Lai and Williams in 1999 [475].

• 3. additive bandwidth, B ⁺(G). For a proper numbering f, $B^+_f(G) = max \{|f(u) + f(v) - (n+1)| : uv \in E\}$. The additive bandwidth $B^+(G) = min \{B^+_f(G) : f$ is a proper numbering of G}; introduced by Bascuñán, Ruiz and Slater in 1992 [34] and further developed by Bascunan et al. in 1995 [35].

• 4. edge bandwidth B′(G). For a proper edge numbering f : E →{1, 2, …, m} of G, define $B^{\prime }_f(G) = max \{|f(e_i) - f(e_j)| : e_i$ adjacent to e _j}. The edge bandwidth is defined as $B'(G) = min \{B^{\prime }_f(G) : f$ is a proper edge numbering of G}; see Jiang et al. [435].

• 5. edge sum or bandwidth sum s(G). For a proper numbering f, define s _f =∑_{uv ∈ E}|f(u) − f(v)|. The edge sum of G is defined as s(G) = min{s _f(G) : f is a proper numbering of G}; introduced by Harper in 1964 [349].

• 6. cutwidth cutw(G). For a proper numbering f and for every 1 ≤ i < n, define E _i = {uv ∈ E : f(u) ≤ i < f(v)}. The cutwidth of f is cutw(f) = max{|E _i| : 1 ≤ i < n}. The cutwidth of G is cutw(G) = min{cutw(f) : f is a proper numbering of G}; cf. Korach and Solel [460]. One can also define the minimum cutwidth of a proper numbering f to be mincutw(f) = min{|E _i| : 1 ≤ i < n}. The maximinimal cutwidth, maxmincutw(G) = max{mincutw(f) : f is a proper numbering of G}.

• 7. MAX CUT, or maxcut(G), the maximum number of edges between V ₁ and V ₂ in a bipartition of V . Equivalently, maxcut(G) equals the maximum number of bicolored edges in a 2 coloring of the vertices of G. This is a standard NP-complete problem, found in Garey and Johnson, as problem ND17, on p.210 of [281]. See also the upper edge connectivity λ ⁺(G) in Section 3.2.

• 8. (vertex) irregularity strength vs(G). An edge k-labeling of a graph G is a function λ : E →{1, 2, …, k}. An edge k-labeling λ is called vertex irregular if for every v ∈ V , wt(v) =∑_{uv ∈ E} λ(uv) is unique, that is, for no two vertices u and v is wt(u) = wt(v). The vertex irregularity strength vs(G) equals the minimum k such that G has a vertex irregular k-labeling; introduced by Chartrand, Jacobson, Lehel, Oellermann, Ruiz, and Saba in 1988 [119]. See also Ebert et al. [216].

• 9. (edge) irregularity strength es(G). A vertex k-labeling λ : V →{1, 2, …, k} is called edge irregular if for every edge uv ∈ E, wt(uv) = λ(u) + λ(v) is unique, that is, for no two edges e, e′∈ E is wt(e) = wt(e′). The edge irregularity strength es(G) equals the minimum integer k such that G has an edge irregular k-labeling; introduced by Chartrand et al. in 1988 [119]: see also Al-Mushayt [7].

• 10. total vertex irregularity strength tvs(G). A total k-labeling of a graph G is a function λ : V ∪ E →{1, 2, …, k}. A total k-labeling λ is called vertex irregular if for every v ∈ V , wt(v) = λ(v) +∑_{uv ∈ E} λ(uv) is unique, that is, for no two vertices u and v is wt(u) = wt(v). The total vertex irregularity strength tvs(G) equals the minimum k such that G has a total vertex irregular k-labeling; introduced by Bača, Jendrol, Miller and Ryan in 2007 [29]; see also Nurdin et al. [516].

• 11. total edge irregularity strength tes(G). A total k-labeling of a graph G is a function λ : V ∪ E →{1, 2, …, k}. A total k-labeling λ is called edge irregular if for every uv ∈ E, wt(uv) = λ(u) + λ(uv) + λ(v) is unique, that is, for no two edges e, e′∈ E is wt(e) = wt(e′). The total edge irregularity strength tes(G) equals the minimum k such that G has a total edge irregular k-labeling; introduced by Bača, Jendrol, Miller, and Ryan in 2007 [29].

• 12. profile P(G). For a proper numbering f and for every v ∈ V , define the profile of a vertex v ∈ V  to be p _f(v) = max{{0}∪{f(v) − f(x)| : x ∈ N(v)}}. Define P _f(G) =∑_{v ∈ V} p _f(v). The profile P(G) = min{P _f(G) : f a proper numbering of G}; see Lin and Yuan [487] and Lai and Williams [475].

• 13. topological bandwidth B ^∗(G). We say that a graph G′ is a refinement of a graph G if G′ can be obtained from G by subdividing some subset of the edges E(G). The topological bandwidth B ^∗(G) = min{B(G′) : G′ is a refinement of G}; introduced by Makedon, Papadimitriou, and Sudborough in 1983 [495], see also Kloks and Tan [456].

3.5 Decomposition and Partition Numbers

Most of the parameters in this subsection involve either a (vertex) partition π = {V ₁, V ₂, …, V _k} or an (edge) partition π′ = {E ₁, E ₂, …, E _k} so that each set V _i or E _i has some given property. The remaining parameters involve a family of not necessarily disjoint subsets of a graph whose union is the entire set, and which has some given property.

• 1. (vertex) arboricity va(G), minimum order of a partition π = {V ₁, V ₂, …, V _k} into forests, that is, the subgraph G[V _i] induced by each set V _i is a disjoint union of trees; introduced and studied by Nash-Williams in 1964 [512],and Raspaud and Wang in 2008 [537].

• 2. tree vertex covering number or tree arboricity ta(G), minimum order of a partition π = {V ₁, V ₂, …, V _k} into trees, that is, the subgraph G[V _i] induced by each set V _i is a tree. See Foregger and Foregger [268].

• 3. tree edge covering number or tree edge arboricity ta′(G), minimum order of a partition π = {E ₁, E ₂, …, E _k} into trees, that is, the subgraph G[E _i] induced by each set E _i is a tree. See Chung [438].

• 4. linear arboricity la(G), minimum order of a partition π′ = {E ₁, E ₂, …, E _k} into linear forests, that is, each component in each edge-induced subgraph G[E _i] is a path; introduced and studied by Akiyama, Exoo, and Harary in 1981 [6], and Alon in 1988 [13].

• 5. star arboricity st(G), minimum order of a partition π′ = {E ₁, E ₂, …, E _k} into star forests. A star forest or galaxy is a forest (acyclic graph) whose components are stars; introduced by Algor and Alon in 1989 [12]; see also Hakimi, Mitchem, and Schmeichel [328], who show that every planar graph has star arboricity at most 5.

• 6. star partition number γ ^∗(G), minimum order of a partition π = {V ₁, V ₂, …, V _k}, such that the subgraph induced by every set V _i is a star; introduced by Walikar [633].

• 7. clique edge partition number cep(G) or clique edge covering number cc(G), minimum order k of an edge partition π = {E ₁, E ₂, …, E _k} such that for 1 ≤ i ≤ k, the induced graph G[E _i] is a complete subgraph, or clique, or equivalently, the minimum number of pairwise-disjoint cliques which contain every edge. See surveys by Pullman in 1983 [527] and Monson, Pullman, and Rees in 1995 [509], the latter of which contains a bibliography of 131 publications on the topic and over 30 open problems.

• 8. clique vertex partition number cvp(G) or clique vertex covering number, minimum order k of an vertex partition π = {V ₁, V ₂, …, V _k} such that for 1 ≤ i ≤ k, the induced graph G[V _i] is a complete subgraph, or clique. Note that a clique vertex partition of a graph G is a proper coloring in the complement $\overline {G}$ of G. See surveys by Pullman [527] and Monson et al. [509].

• 9. k-defective colorings. A graph G has a k-defective coloring of order m if it has a vertex partition π = {V ₁, V ₂, …, V _m} such that for all 1 ≤ i ≤ m, Δ(G[V _i]) ≤ k. The k-defective coloring number D _k(G) equals the minimum integer m such that G has a k-defective coloring of order m; introduced by Cowen, Cowen, and Woodall in 1986 [174]; see also Archdeacon [19]. It follows, therefore, that for 0 ≤ k ≤ Δ(G), 1 = D _Δ(G)(G) ≤ D _k(G) ≤ D ₀(G) = χ(G), where χ(G) is the chromatic number of G.

• 10. tree width. A tree decomposition of a graph G = (V, E) is a tree T(G) with vertices in order V (T(G)) = {V ₁, V ₂, …, V _p} having the following three properties: (i) $\bigcup _{1}^{p} V_i = V(G)$, (ii) for every edge uv ∈ E(G), there is an i such that u, v ∈ V _i, and (iii) for every 1 ≤ i ≤ j ≤ k ≤ p, V _i ∩ V _k ⊆ V _j. It is important to point out that the significance of Condition (iii) is that for every vertex v ∈ V (G), the set of vertices V _i ∈ E(T(G)) which contain vertex v forms a subtree of T(G). The width of a tree decomposition $tw(T(G)) = \max \{|V_i| - 1 : 1 \leq i \leq p \}$. The tree width tw(G) = min{tw(T(G)) : T(G) is a tree decomposition of G}.

  Earliest references to the concept of tree width include the following by Bertele and Brioshi [48], Halin noticed in 1976 that tree width has properties in common with the Hadwiger number in [330]. But Seymour and Thomas developed a min-max theorem for tree-width in 1993 [568], Robertson and Seymour developed algorithms in 1996 [543] and re-discovered tree width in developing their theory of graph minors in 1984 [542]. More details can be found in the 1994 work of Bodlaender [57]; see also Korach and Solel [460].

• 11. path (decomposition) number, pn(G). A path decomposition is a family of paths such that every edge e ∈ E lies on precisely one path. The path number pn(G) equals the minimum number of paths in a path decomposition of G; perhaps first discussed for directed graphs by Alspach and Pullman in 1974 [15], see also Arumugam et al. [22].

• 12. path width, pw(G) = min{pw(P(G)) : P(G) a path decomposition of G}. The width of a path decomposition $pw(P) = \max \{|V_i| - 1 : 1\leq i \leq p \}$; cf. Korach and Solel [460].

• 13. path length, pl(G) = min{pl(P) : P a path decomposition of G}. The path length of a path decomposition P of G is $pl(P) = max_{1 \leq i \leq p} \{ max_{u,v \in V_i} d(u,v) \}\}$. The reader is referred to Dragan et al. [204].

• 14. path partition number π _p(G), minimum order of a partition π = {V ₁, V ₂, …, V _k} such that each induced subgraph G[V _i] contains a spanning, or Hamiltonian, path; cf. Vu Dinh [631].

• 15. induced path partition number π _ip(G), minimum order of a vertex partition π = {V ₁, V ₂, …, V _k} such that each induced subgraph G[V _i] is a path; cf. Broere et al. [84].

3.6 Covering, Packing, Independence, and Matching Numbers

A set S ⊆ V  of vertices is independent if no two vertices in S are adjacent, and a set M ⊆ E of edges is independent or a matching if no two edges in M are adjacent, that is, have a vertex in common. Given a matching M, V [M] is the set of vertices incident with an edge in M, and G[V (M)] is the subgraph induced by the vertices in V (M). A graph G of even order n = 2k has a perfect matching if it has a matching M of cardinality k.

A set S of vertices or edges is said to cover another set T if every element of T either contains an element of S or is adjacent or incident to an element of S.

All of the parameters in this subsection have to do with sets that are independent or cover other sets. These include some of the most basic of all parameters in graph theory.

• 1. vertex independence numbers i(G) and α(G), minimum and maximum cardinality of a maximal independent set. While the notation i(G) is fairly standard for the independent domination number, many papers denote the vertex independence number by β ₀(G).

• 2. k-dependence number α _k(G), maximum cardinality of a set S such that for every vertex u ∈ S, |N(u) ∩ S|≤ k; introduced by Fink and Jacobson in 1985 [264], whose conjecture, that the k-domination number γ _k(G) [defined below] is a lower bound for the k-dependence number, was proved by Favaron in 1985 [248]. Improved lower bounds for α _k(G) were obtained by Favaron in 1988 [249] and Caro and Tuza in 1991 [99]. It is worth mentioning that today most authors refer to sets S ⊆ V  that are k-independent, for positive integers k, meaning that the maximum degree of the induced subgraph G[S] is at most k − 1. Thus, k-independent sets are precisely (k − 1)-dependent. The reader is referred to the 2012 survey by Chellali et al. [138].

• 3. vertex covering numbers β(G) and β ⁺(G), minimum and maximum cardinality of a minimal vertex cover, that is, a set of vertices S such that for every edge uv ∈ E, {u, v}∩ S ≠ ∅. We note that in many papers the vertex covering number is denoted by α(G). It should be noted that by a well-known theorem of Gallai, for any graph G of order n, α(G) + β(G) = n.

• 4. edge covering numbers β′(G) and β ^′+(G), minimum and maximum cardinality of a minimal edge cover, that is, a set M of edges such that every vertex v ∈ V  is incident with at least one edge in M.

• 5. triangle cover number τ ₃(G), minimum cardinality of triangle cover, that is, a set F ⊂ E of edges such that every triangle in G contains an edge in F. See Tuza [616] and Yuster [647].

• 6. triangle packing number ν ₃(G), maximum cardinality of a set of pairwise edge-disjoint triangles. See Tuza [616], who conjectured that for every graph G, τ ₃(G) ≤ 2ν ₃(G). See also Yuster [647].

• 7. clique covering number cc(G). A clique covering is a set of cliques containing every edge at least once.

  See Orlin [518].

• 8. clique packing number cp(G). A clique packing is a collection of cliques containing every edge at most once.

• 9. 2-packing numbers p ₂(G) and P ₂(G), minimum and maximum cardinality of a maximal 2-packing in G, that is, a set S such that for every vertex v ∈ V , |N[v] ∩ S|≤ 1. Equivalently, a 2-packing can be defined as a set S having the property that for any two vertices u, v ∈ S, d(u, v) > 2. From this, one can naturally define a k-packing to be a set S having the property that for any two vertices u, v ∈ S, d(u, v) > k.

• 10. matching numbers α ^′−(G) and α′(G), minimum and maximum cardinality of a maximal matching in G. It should be noted that by a well-known theorem of Gallai, for any graph G of order n with no isolated vertices, α′(G) + β′(G) = n. In many papers, the matching number is denoted by β ₁(G). As far as we know, the parameter α ^′−(G), called the lower matching number has not been studied very much.

• 11. induced, or strong, matching number, α ^∗(G), maximum cardinality of a matching M such that the subgraph G[V (M)] consists of disjoint K ₂’s, or equivalently, no edge in E − M connects two edges in M. This was introduced by Cameron in 1989 [95], and further studied by Horák et al. in 1993 [422], by Golumbic and Laskar in 1993 [307], and by Brandstädt and Mosca in 2011 [73].

• 12. disconnected matching number $\alpha ^{\prime }_{dc}(G)$, maximum number of edges in a matching M such that the subgraph G[V (M)] is disconnected; cf. Goddard et al. [298].

• 13. forcing matching number. Let G be a graph that admits a perfect matching. The forcing number of a perfect matching M of G is defined as the smallest number of edges in a subset S ⊆ M, such that S is in no other perfect matching; introduced by Harary, Klein, and Zívković in 1991 [346], and further studied by Pachter and Kim in 1998 [519].

• 14. anti-forcing matching number of a perfect matching M in a graph G is defined as the minimum number of edges not in M, whose deletion results in a graph G′ having only M as a perfect matching. The minimum (resp. maximum) anti-forcing number of G is the minimum (resp. maximum) anti-forcing number of all perfect matchings M in G. It is shown by Deng and Zhang that the maximum anti-forcing number of a graph is at most its cyclomatic number, and the graphs with maximum anti-forcing number achieving the upper bound are characterized;introduced by Deng and Zhang in 2017 [192].

• 15. isolate-free matching number $\alpha ^{\prime }_{if}(G)$, maximum number of edges in a matching M such that either |M| = 1 or the subgraph G[V (M)] contains no K ₂ component; cf. Goddard et al. [298].

• 16. acyclic matching number, $\alpha ^{\prime }_{ac}(G)$, maximum cardinality of an acyclic matching M, that is, a matching M such that the subgraph G[V (M)] is acyclic; introduced by Goddard et al. in 2005 [298].

• 17. matchability number μ(G), minimum cardinality of a maximal matchable set of vertices in G. A set S of vertices is called matchable if there exists an injection ϕ : S → V − S such that for every vertex u ∈ S, u is adjacent to ϕ(u); introduced by Cockayne, Hedetniemi and Laskar in 1998 [164], and further studied by Dean et al. [186].

• 18. uniquely restricted matching number $\alpha ^{\prime }_{ur}(G)$, maximum cardinality of a matching M such that G[V (M)] has exactly one maximum matching, or equivalently, G[V (M)] does not contain a cycle, the edges of which alternate between edges in M and edges not in M. This was introduced by Golumbic, Hirst, and Lewenstein in 2001, see also Mishra [506].

3.7 Coloring Numbers

In this subsection, a vertex k-coloring is simply a vertex partition π = {V ₁, V ₂, …, V _k} into k color classes V _i, for 1 ≤ i ≤ k. We say that a vertex v ∈ V _i is colored i or assigned the color i. Virtually all of the vertex coloring numbers in this subsection have in common that they equal the minimum or maximum order k of a coloring such that each color class V _i has some property $\mathcal {P}$. A coloring is called proper if every V _i is an independent set.

An edge k-coloring is defined similarly, namely an edge partition

π′ = {E ₁, E ₂, …, E _k} into k color classes E _i.

• 1. chromatic number χ(G), minimum order k of a proper vertex coloring π = {V ₁, V ₂, …, V _k} of G. If π is a proper coloring of G with χ(G) = k colors, then the same partition is a partition of the complement $\overline {G}$ of G into complete subgraphs, called a clique partition, as defined and discussed in Section 3.6. The reader is referred to the book on graph coloring by Chartrand and Zhang [118] and the large collection of 200 graph coloring problems in the 1995 book by Jensen and Toft [434].

• 2. Grundy number Γr(G), maximum order of a proper coloring π = {V ₁, V ₂, …, V _k}, such that for every i, 2 ≤ i ≤ k, every vertex in V _i is adjacent to at least one vertex in every V _j, for all 1 ≤ j < i; named after a paper by P. M. Grundy in 1939 [316], and introduced by Christen and Selkow in 1979 [153]; see also Hedetniemi et al. [382] and Zaker [648]. Grundy colorings are also called greedy colorings, which result from the process of arbitrarily ordering the vertices v ₁, v ₂, …, v _n, coloring vertex v ₁ with color 1, and then for i = 2 to n, coloring vertex v _i with the smallest color not used to color a vertex adjacent to v _i. The Grundy number is the maximum number of colors that can be used in any greedy coloring of G.

• 3. partial Grundy number ∂Γr(G), maximum order of a proper coloring π = {V ₁, V ₂, …, V _k}, such that for every i, 2 ≤ i ≤ k, there exists at least one vertex in V _i, called a Grundy vertex, that is adjacent to at least one vertex in every V _j, for all 1 ≤ j < i ≤ k; introduced by Erdös, Hedetniemi, Laskar, and Prins in 2003 [233]. See also Shi et al. [579], Effantin and Kheddouci [220], and Balakrishnan and Kavaskar [31]. Note that in a Grundy coloring, all vertices are Grundy vertices, but in a partial Grundy coloring, each color class is required to have only one Grundy vertex.

• 4. achromatic number ψ(G), maximum order of a complete proper coloring of G. A partition π = {V ₁, V ₂, …, V _k} is called complete if for every pair of distinct color classes V _i and V _j, 1 ≤ i < j ≤ k, there is a vertex in V _i that is adjacent to a vertex in V _j; introduced by Harary and Hedetniemi in 1970 [342]. See also Cairnie and Edwards [94], and Hughes and MacGillivray [428].

• 5. pseudo-achromatic number ψ _s(G), maximum order of a complete coloring of G; introduced by Gupta in 1969 [318]. See also Bhave [49], Edwards [218] and Hedetniemi [379]. Note than all proper colorings of a graph with χ(G) colors, all Grundy colorings, and all partial Grundy colorings are complete colorings. Therefore, for any graph G,

  $$\displaystyle \begin{aligned}\chi(G) \leq \varGamma r(G) \leq \partial \varGamma r(G) \leq \psi(G) \leq \psi_s(G).\end{aligned}$$

• 6. acyclic chromatic number a(G), minimum number of colors in a proper coloring π = {V ₁, V ₂, …, V _k} such that for any two color classes V _i and V _j, the bipartite subgraph induced by V _i ∪ V _j is acyclic; introduced by Grunbaum in 1973 [315]. See also Borodin [67] and Goddard [293]. In his original paper Grünbaum conjectured that for any planar graph G, a(G) ≤ 5; this was later proved correct by Borodin in 1979 [67].

• 7. acyclic chromatic index a′(G), minimum order of a proper edge coloring π′ = {E ₁, E ₂, …, E _k} such that for every 1 ≤ i < j ≤ k, the induced subgraph G[E _i ∪ E _j] is acyclic, or equivalently, such that every cycle contains edges with at least three different colors; introduced in 1978 and 1980 by Fiamčík [259, 260].

• 8. b-chromatic number χ _b(G), maximum order of a proper coloring

  π = {V ₁, V ₂, …, V _k} such that every set V _i contains at least one colorful vertex. A vertex v ∈ V _i is colorful if it is adjacent to at least one vertex in every color class V _j, j ≠ i; introduced by Irving and Manlove in 1999 [430]. See also Kouider and Mahéo [463].

• 9. broadcast chromatic number χ _b(G), minimum order of a proper vertex coloring π = {V ₁, V ₂, …, V _k}, such that for 1 ≤ i ≤ k, the set V _i is an i-packing, that is, for any two vertices u, v ∈ V _i, d(u, v) > i. It can be seen that for any graph G, χ _b(G) ≤ β(G) + 1, where β(G) is the vertex covering number of G. This was introduced by Goddard et al. [299], who showed that for any infinite grid graph G, χ _b(G) ≤ 23. This has subsequently been improved by several authors, the most recent, by Martin et al. [498] who show that . The most recent papers on this parameter call this the packing chromatic number χ _ρ(G).

• 10. chromatic sum χ _σ(G), minimum sum of all of the colors used in a proper vertex coloring of G with positive integers; introduced by Erdös, Kubicka and Schwenk in 1990 [231] and further studied by Kubicka in 2004 [468] and in 2005 [469].

• 11. cd-chromatic number χ _cd(G), minimum order k of a proper coloring π = {V ₁, V ₂, …, V _k} such that for every 1 ≤ i ≤ k, there exists a vertex u _i ∈ V  such that u _i dominates V _i, that is, u _i is adjacent to every vertex in V _i. These are called cd-colorings; introduced by Venkatakrishnan and Swaminathan in 2014 [620]. See also Shalu et al. in 2017 [574] and Krithika et al. in 2017 [465].

• 12. chromatic dimension dim(G). Let S = {v ₁, v ₂, …, v _k} be a vertex set in a connected graph G. For each vertex v ∈ V , define the code

  $$\displaystyle \begin{aligned}c(v,S) = (d(v,v_1), d(v, v_2), \ldots, d(v, v_k)).\end{aligned}$$

  The set S is a proper S-coloring of G if distinct vertices have distinct codes. A proper S-coloring of minimum cardinality k is called a color basis for G and the number of vertices in a color basis is called the chromatic dimension dim(G); introduced by Chartrand and Zhang in 2000 [116].

• 13. circular chromatic number χ _c(G). Let $\mathcal {A}_r$ denote the set of open, unit length arcs of a circle C of Euclidean length r. An r-circular coloring of a graph G is a function $c : V \rightarrow \mathcal {A}_r$ such that for every uv ∈ E, c(u) ∩ c(v) = ∅. A graph G is r-circular colorable if it has an r-circular coloring. The circular chromatic number χ _c(G) = inf{r : G is r-circular colorable }; introduced by Vince in 1988 [623]. It can be seen that for any finite graph, the circular chromatic number is always rational and χ(G) − 1 ≤ χ _c(G) ≤ χ(G). The reader is referred to an extensive survey by Zhu [662] which contains, among other things, many conjectures and some 28 open problems about the circular chromatic number; see also Junosza-Szaniawski [437] and Zhu [660].

• 14. co-chromatic number z(G), minimum order k of a coloring π = {V ₁, V ₂, …, V _k} such that for every 1 ≤ i ≤ k, the induced subgraph G[V _i] is either a complete graph or an empty graph (that is, V _i is an independent set); introduced by Lesniak-Foster and Straight in 1977 [482], who showed that if G is triangle-free, then z(G) = χ(G). See also PhD thesis by Gimbel [290], Erdös et al. [230], and Chudnovsky [154].

• 15. degree-bounded chromatic number. A degree-bounded coloring is a proper coloring db : V →{1, 2, …, Δ(G)} having the property that for every vertex v ∈ V , db(v) ≤ deg(v). The db-chromatic number χ _db(G) equals the minimum integer k such that G is db-colorable using only the colors 1, 2, …, k. Note, not every graph is db-colorable; introduced by Hakimi, Mitchem, and Schmeichel in 1995 [327]. The authors show that if a connected graph G has a block, that is neither a complete graph nor an odd cycle, then G is db-colorable.

• 16. distance-s chromatic number χ _s(G). An L _s -coloring is a proper coloring c : V →{1, 2, …, n} such that for all u, v ∈ V , c(u) = c(v) implies d(u, v) ≥ s + 1. The s-chromatic number χ _s(G) equals the minimum integer s such that G has an s-coloring; introduced by Speranza in 1975 [595]. See also Gionfriddo [292] and Marino and Puccio [497].

• 17. distinguishing chromatic number χ _D(G). A proper vertex k-coloring c : V →{1, 2, …, k} is said to be k-distinguishing if the only automorphism of G that preserves all vertex colors is the identity. The distinguishing chromatic number χ _D(G) equals the minimum k such that G has a distinguishing proper k-coloring; introduced by Collins and Trenk in 2006 [173].

• 18. distinguishing number D(G). A labeling h : V →{1, 2, …, k} is said to be k-distinguishing if the only automorphism of G that preserves all vertex labels is the identity. The distinguishing number D(G) equals the minimum k such that G has a k-distinguishing labeling; introduced by Albertson and Collins in 1996 [10].

• 19. dominator chromatic number χ _d(G). A dominator coloring of a graph G is a proper coloring π = {V ₁, V ₂, …, V _k} such that for every vertex v ∈ V , there exists a set V _i such that v is adjacent to, or dominates, every vertex in V _i. The dominator chromatic number χ _d(G) equals the minimum order of a dominator coloring of G; suggested by Hedetniemi, Hedetniemi, McRae and Blair in [393] but introduced by Gera, Rasmussen, and Horton in 2006 [286], and further studied by Gera in 2007 [284, 285], Chellali and Maffray in 2012 [136], and Arumugam et al. in [24, 25].

• 20. edge chromatic number or chromatic index χ′(G), minimum order of an edge partition π′ = {E ₁, E ₂, …, E _k}, such that every set E _i is an independent set of edges, i.e. a matching; perhaps first studied by Vizing in 1965 [626], who showed that for every nonempty graph G, χ′(G) ≤ 1 + Δ(G). See also Fiamčík and Jucović [261] and Alavi and Behzad [8].

• 21. fall chromatic number χ _f(G). A vertex v ∈ V _i in a proper k-coloring π = {V ₁, V ₂, …, V _k} is called colorful if it is adjacent to at least one vertex in every color class V _j, i ≠ j. A fall coloring is a coloring in which every vertex is colorful. The fall chromatic number χ _f(G) and fall achromatic number ψ _f(G) equal the minimum and maximum integer k for which G has a fall coloring; introduced by Dunbar, Hedetniemi, Hedetniemi, Jacobs, Knisely, Laskar, and Rall in 2000 [213]. It should be noted that not every graph has a fall coloring. See also Shaebani [569].

• 22. fractional chromatic number χ _f(G). Let $\mathcal {I}$ denote the family of all independent sets in a graph G. A fractional coloring of G is a function $c : \mathcal {I} \rightarrow [0, 1]$ such that for every v ∈ V , $\sum _{S \in \mathcal {I} x \in S} c(S) = 1$. The value of a fractional coloring c is $\sum (c) = \sum _{S \in \mathcal {I}} c(S)$. The fractional chromatic number $\chi _f(G) = inf \{\sum (c) : c \mbox{ is a fractional coloring of G} \}$; introduced as the multicoloring number by Hilton, Rado, and Scott in 1973 [417] and as the set chromatic number by Bollobás and Thomassen in 1979 [63]. See also the book by Scheinerman and Ullman [562].

• 23. forcing chromatic number F _χ(G), minimum integer k such that there is a set of k vertices in G and a coloring of those k vertices that extends uniquely to a proper s-coloring of G, where χ(G) = s; introduced by Harary in [340]. See also Pachter and Kim in [519].

• 24. harmonious chromatic number h(G). A harmonious k-coloring is a proper coloring π = {V ₁, V ₂, …, V _k} with the added property that between any two color classes V _i and V _j there can be at most one edge. The harmonious chromatic number h(G) equals the minimum integer k for which G has a harmonious coloring. This concept appears to have been independently discovered by Harary and Plantholt in 1982 [345] and Hopcroft and Krishnamoorthy in 1983 [420]. Lee and Mitchem [478] have shown that for any graph G, $1 + \varDelta (G) \leq h(G) \leq (1 + \varDelta (G)^2) \lceil \sqrt {n} \rceil$; see also Edwards [217] and Edwards and McDiarmid [219].

• 25. upper harmonious chromatic number H(G). A harmonious k-coloring π = {V ₁, V ₂, …, V _k} is called minimal if the partition which results by combining any two color classes into one, V _i ∪ V _j, is no longer a harmonious coloring. The upper harmonious chromatic number H(G) equals the maximum integer k for which G has a minimal harmonious k-coloring. This was introduced by Chen, Domke, Hattingh, and Laskar in 1999 [148]; see also Hattingh et al. [353].

• 26. line-distinguishing chromatic number or harmonic (chromatic) number h′(G), the minimum number of colors which can be assigned to the vertices of a graph G such that no two edges receive the same color pair. A line-distinguishing coloring need not be a proper coloring, but if not, then for each color, at most one edge can receive an identical color pair with that color. Stated, equivalently, a line-distinguishing coloring is a vertex partition π = {V ₁, V ₂, …, V _k} such that for every 1 ≤ i ≤ k, the induced subgraph G[V _i] can contain at most one edge, and between any two color classes V _i and V _j there can be at most one edge. Thus, a line-distinguishing coloring which is also a proper coloring is called a harmonious coloring. This idea and name was introduced by Harary and Plantholt in 1982 [345] but the same idea was independently discovered by Hopcroft and Krishnamoorthy in 1983 [420]. One can show that for any graph G, Δ(G) ≤ h′(G) ≤ h(G). See also Salvi [551].

• 27. upper line-distinguishing chromatic number H′(G). A line-distinguishing k-coloring π = {V ₁, V ₂, …, V _k} is called minimal if the partition which results by combining any two color classes into one, V _i ∪ V _j, is no longer a line-distinguishing coloring. The upper line-distinguishing chromatic number H′(G) equals the maximum integer k for which G has a minimal line-distinguishing k-coloring. This was introduced by Chen, Domke, Hattingh, and Laskar in 1999 [148]; see also Hattingh et al. [353].

• 28. incidence chromatic number χ _i(G). An incidence in a graph G is a pair (v, e) where vertex v is incident to edge e. Two incidences (u, e) and (v, f) are adjacent if either (1) u = v, (2) e = f, (3) uv = e or (4) uv = f. An incidence coloring is an assignment of colors to the incidences such that adjacent incidences are assigned different colors. The incidence chromatic number χ _i(G) equals the minimum number of colors required to color the incidences of G; introduced by Brualdi and Massey in 1993 [86]. See also Gregor et al. [312]. It is complex to see, but it appears that χ _i(G) = χ(L(S(G))²), where L(G) is the line graph of G, S(G) is the subdivision graph of G, and G ² denotes the square of a graph G.

• 29. interval chromatic number. Let G = (V, E) be a graph with a nonnegative weight function wt defined on the vertices in V . An interval coloring assigns to each vertex v ∈ V  an open interval of size wt(v), such that if two vertices u, v are adjacent, then the corresponding intervals do not intersect. The size of an interval coloring is the total size of the union of all assigned intervals. The minimum possible size of an interval coloring is the interval chromatic number. Stockmeyer (cf. Golumbic [306]) proved that determining the interval chromatic number of NP-complete even if G is an interval graph and wt is restricted to the values 1 and 2; see also Shalom [573].

• 30. irregular chromatic number χ _ir(G). Let c : V (G) →{1, 2, …, k} be a proper vertex k-coloring of a graph G. Let code(v) = (a ₀, a ₁, …, a _k), where a ₀ = c(v) and for 1 ≤ i ≤ k, a _i equals the number of neighbors of v colored i. The coloring c is called irregular if distinct vertices have distinct codes, that is, u ≠ v implies code(u) ≠ code(v). The irregular chromatic number χ _ir(G) equals the minimum k such that G has an irregular k-coloring; introduced by Radcliffe and Zhang in 2006 [531].

• 31. irredundant chromatic number χ _irr(G). A set S is an irredundant set if for every vertex v ∈ S, pn[v] = N[v] − N[S −{v}] ≠ ∅. An irredundant k-coloring of a graph G is a vertex partition π = {V ₁, V ₂, …, V _k} such that for all 1 ≤ i ≤ k, V _i is an irredundant set. The irredundant chromatic number χ _irr(G) equals the minimum order k of an irredundant k-coloring; introduced by Haynes, Hedetniemi, Hedetniemi, McRae, and Slater in 2008 [369]. Notice that every proper coloring is an irredundant coloring, since every independent set is irredundant. Thus,it follows that for any graph G, χ _irr(G) ≤ χ(G).

• 32. open irredundant chromatic number χ _oir(G). A set S is an open irredundant set if for every vertex v ∈ S, pn(v) = N(v) − N[S −{v}] ≠ ∅. An open irredundant k-coloring of a graph G is a vertex partition π = {V ₁, V ₂, …, V _k} such that for all 1 ≤ i ≤ k, V _i is an open irredundant set. The open irredundant chromatic number χ _oir(G) equals the minimum order k of an open irredundant k-coloring, or the minimum order of a vertex partition into open irredundant sets; cf. Arumugam et al. [23].

• 33. L(2, 1)-labeling number or L(2, 1)-coloring number λ(G), minimum value k of a proper k-coloring f : V →{0, 1, 2, …, k}, such that if any two vertices u and v are adjacent then |f(u) − f(v)|≥ 2, and if d(u, v) = 2, then f(u) ≠ f(v). The basic ideas for L(2, 1)-colorings originated with Hale in 1980 [329]; but was introduced for study by Yeh in 1990 [643] and Griggs and Yeh in 1992 [313]. See also Klavzar and Spacapan [454].

• 34. list chromatic number χ _l(G), minimum integer k such that if every vertex v ∈ V  is assigned a list L(v) of at least k distinct colors, then G has a proper vertex coloring, where the color chosen for every vertex v is an element of L(v); introduced by Vizing in 1976 [628] and independently by Erdös, Rubin and Taylor in 1979 [227].

• 35. list edge chromatic number, or list chromatic index $\chi ^{\prime }_l(G)$, minimum integer k such that if every edge e ∈ E is assigned a list L(e) of at least k distinct colors, then G has a proper edge coloring, where the color chosen for every edge e is an element of L(e); cf. Bollobás and Harris in 1985 [62], cf. also Galvin [279] and Slivnik [592].

• 36. neighborhood-restricted achromatic number or [≤ k]-achromatic number ψ _[≤k](G). Given a vertex partition π = {V ₁, V ₂, …, V _k}, let deg _π[v] = |{i : N[v] ∩ V _i ≠ ∅}|. A partition π is said to be a [≤ k]-coloring if for every v ∈ V , deg _π[v] ≤ k, that is, no vertex is adjacent to more than k distinctly colored vertices. The [≤ k]-achromatic number ψ _[≤k](G) is the maximum order of a [≤ k]-coloring of G; introduced by Chandler, Desormeaux, Haynes, and Hedetniemi in 2016 [107].

• 37. packing chromatic number. This is the same parameter as the broadcast chromatic number χ _b(G), defined above, but called this by Korže and Vesel [461].

• 38. proper connection number pc(G) and strong proper connection number spc(G). Let G be a connected, arbitrarily edge-colored graph. A path P in G is called a proper path if no two adjacent edges of P are colored the same. A proper u − v geodesic is a proper path of length d(u, v). An edge coloring c is called a proper-path coloring if every pair of vertices u, v ∈ V  are connected by a proper path, and is called a strong proper-path coloring if every pair u, v of vertices are connected by a proper u − v geodesic. The minimum number of colors in a proper-path coloring is called the proper connection number pc(G) and the minimum number of colors in a strong proper-path coloring is called the strong proper connection number spc(G). These coloring numbers are related to the rainbow connection number rc(G), and strong rainbow connection number src(G); cf. Andrews et al. [17] and Lumduanhom et al. [491].

• 39. quorum coloring number ψ _q(G), maximum order k of a partition π = {V ₁, V ₂, …, V _k} such that for every vertex 1 ≤ i ≤ k, every vertex v ∈ V _i satisfies |N[v] ∩ V _i|≥|N[v]|∕2, that is, at least half of the vertices in the closed neighborhood of every vertex v have the same color as v; introduced by Hedetniemi, Hedetniemi, Laskar, and Mulder in 2013 [398]. Quorum colorings are very similar to satisfactory partitions due to Shafique and Dutton [570] in which the condition is that at least half of the vertices in the open neighborhood of every vertex v have the same color as v. Since not all graphs have a satisfactory partition, for example complete graphs, the primary focus of research on satisfactory partitions is to decide if an arbitrary graph G has a satisfactory partition and to find classes of graphs that do or do not have them. On the other hand, since all graphs have quorum colorings, the primary focus of quorum colorings is on determining the maximum order of a quorum coloring of a given graph.

• 40. radio number rn(G). A radio labeling c of a connected graph G is an assignment of distinct positive integers to the vertices v ∈ V  such that d(u, v) + |c(u) − c(v)|≥ 1 + diam(G), for every two distinct vertices u, v ∈ V . The radio number rn(c) of a radio labeling c is the maximum integer assigned to a vertex v ∈ V . The radio number rn(G) = min{rn(c) : c a radio labeling of G}. This concept was introduced by Chartrand, Erwin, Zhang, and Harary in 2001 [126].

• 41. rainbow connection number rc(G) or strong rainbow connection number src(G), minimum number of colors required to color the edges of a connected graph G so that between any pair of vertices u and v, there is a u − v path, or u − v geodesic, no two edges of which are colored the same; introduced by Chartrand, Johns, McKeon and Zhang in 2008 [132]. See also Li et al. [486], Hao [335], Caro et al. [101], and Schiermeyer [563].

• 42. rank number and arank number χ _r(G) and ψ _r(G). A proper coloring c : V →{1, 2, …, k} is a k-ranking if c(u) = c(v) implies that every u − v path contains a vertex w such that c(w) > c(u). A k-ranking is minimal if decreasing the value c(u) assigned to any vertex u ∈ V  produces a coloring that is not a k-ranking. The rank number χ _r(G) and the arank number ψ _r(G) equal the minimum and maximum k, respectively, such that G has a minimal k-ranking; cf. Iyer et al. [432], de la Torre et al. [184] and Ghoshal et al. [289].

• 43. strong chromatic index $\chi _s^{\prime }(G)$, minimum number of colors that can be used in a proper edge coloring of G so that for every vertex v ∈ V , the set C(v) of colors incident to vertex v is unique; introduced by Burris and Schelp in 1997 [92]. See also Togni [612].

• 44. strong chromatic number χ _s(G), minimum order of a proper coloring π = {V ₁, V ₂, …, V _k} having the property that for every 1 ≤ i ≤ k, no vertex v ∈ V  has two neighbors in V _i; this is equivalent to saying that no vertex has two neighbors with the same color, or that every set V _i is a 2-packing; introduced by Sampathkumar and Pushpa Latha in 1995 [555]. See also Narahari et al. [593].

• 45. strong chromatic index $\chi _s^{\prime }(G)$. A strong edge coloring of a graph G is a proper edge coloring such that every color class is an induced, or strong, matching in G, or equivalently, if no edge is adjacent to two edges with the same color. The strong chromatic index $\chi ^{\prime }_s(G)$ equals the minimum number of colors in a strong edge coloring of G; introduced by Fouquet and Jolivet in 1983 [269]. This parameter was introduced independently by Faudree et al. [247] and by Horák in 1990 [421]. See also Yang and Zhu [641] and Bensmail et al. [43].

• 46. subchromatic number χ _K(G), minimum order of a partition π = {V ₁, V ₂, …, V _k}, such that the subgraph induced by every set V _i is a disjoint union of complete subgraphs of G; introduced by Albertson, Jamison, Hedetniemi, and Locke in 1989 [11]. See also Gimbel and Hartman [291]. Note the similarity of the subchromatic number and the co-chromatic number, z(G), also defined in this subsection, where each color class is either a complete graph or an independent set. Note that for any graph G:

  $$\displaystyle \begin{aligned}\chi_K(G) \leq z(G) \leq \chi(G) \leq \varGamma r(G) \leq \partial \varGamma r(G) \leq \psi(G) \leq \psi_s(G).\end{aligned}$$

• 47. t-tone chromatic number χ _tt(G). For a positive integer t, a t-tone coloring c of a graph G is an assignment of t-element subsets of [k] = {1, 2, …, k} for some integer k > t to the vertices v ∈ V  such that for every two vertices u, v ∈ V , if d(u, v) = d, then |c(u) ∩ c(v)| < d. The t-tone chromatic number χ _tt(G) equals the minimum number of colors in a t-tone coloring of G. The concept of t-tone colorings was introduced by Chartrand in 2009 and first studied by Fonger, Goss, Phillips, and Segroves in [267]. Note that every t-tone coloring is a proper coloring.

• 48. total chromatic number χ ^′′(G), minimum order of a partition of the vertices and edges, Π = {S ₁, S ₂, …, S _k}, such that each set S _i, consisting of a collection of vertices and edges, contains no pair of adjacent vertices, no pair of adjacent edges, and no vertex incident with an edge. Clearly, χ ^′′(G) ≥ Δ(G) + 1. It remains an open conjecture, due independently to Behzad [39] and Vizing [625], that for any graph G, χ ^′′(G) ≤ Δ(G) + 2. See also Campos and de Mello [97], Vijayaditya [622] and Chartrand et al. [133].

• 49. adjacent vertex distinguishing total chromatic number $\chi ^{\prime \prime }_a(G)$. A total coloring c : E ∪ V →{1, 2, …, k} is called adjacent vertex distinguishing if for every edge uv ∈ E, c(u) ∪ c(E(u)) ≠ c(v) ∪ c(E(v)), where E(u) denotes the set of edges incident with vertex u. This concept has been attributed to Zhang, Chen, Li, Yao, Lu and Wang in 2005 [657], but a paper by Chen precedes this by one year [144]. Since then, many papers have been written on these colorings, cf. two recent papers by Hu et al. [426] and by Huang et al. [427].

• 50. vector chromatic number χ _V(G). For t ≥ 2, a vector t-coloring of a graph G with vertex set V = {v ₁, v ₂, …, v _n} consists of an assignment p = (p ₁, p ₂, …, p _n) of real unit vectors to the vertices of V  such that v _i v _j ∈ E if $p_i^T p_j \leq \frac {-1}{t - 1}$. The vector chromatic number χ _V(G) equals the minimum real number t ≥ 2 for which G has a vector t-coloring; introduced by Karger, Motwani, and Sudan in 1994 [443]. See also Godsil et al. [303, 304].

3.8 Domination Numbers

A set S ⊆ V  of vertices is a dominating set if N[S] = V , that is, every vertex in V − S is adjacent to, or equivalently is at distance one from, at least one vertex in S. Thus, if every vertex in S has some desired resource, then every vertex in V − S has easy, one edge access to a vertex in their neighborhood having this resource. From the perspective of vertices in S they have the property that they can ‘observe’ over one edge, every vertex in V − S. The many variations of dominating sets are based on (1) conditions which are placed on the subgraph G[S] induced by a dominating set S, (2) conditions which are placed on the vertices in V − S, or (3) conditions which are placed on the edges between vertices in S and vertices in V − S.

• 1. domination numbers γ(G) and Γ(G), minimum and maximum cardinalities of a minimal dominating set. The reader is referred to the two books on domination in graphs by Haynes, Hedetniemi and Slater in 1998 [361] and in [360].

• 2. enclaveless numbers ψ(G) and Ψ(G), minimum and maximum number of vertices in a maximal enclaveless set. A set S is enclaveless if it does not contain a vertex u ∈ S such that N[u] ⊆ S. It can be seen that for any graph G of order n, γ(G) + Ψ(G) = n, and Γ(G) + ψ(G) = n. It can also be seen that the enclaveless number Ψ(G) also equals the maximum number of pendant edges in a spanning forest of G. The concept of enclaveless sets was introduced by Slater in 1977 [586].

3.8.1 Conditions on S

• 1. independent domination i(G), minimum cardinality of a dominating set that is also independent. Independent domination was introduced by Berge in 1962 [44].

• 2. total domination γ _t(G) and Γ _t(G), minimum and maximum cardinalities of a minimal total dominating set. A set S ⊆ V  of vertices is a total dominating set if N(S) = V , that is, every vertex in V  is adjacent to at least one vertex in S. These parameters were introduced by Cockayne, Dawes, and Hedetniemi in 1980 in [163]. The definitive and most comprehensive treatment of total domination is the book on this subject by Henning and Yeo in 2013 [411].

• 3. connected domination γ _c(G), minimum cardinality of a dominating set S such that the induced subgraph G[S] is connected. This was introduced by Sampathkumar and Walikar in 1979 [558]. One can also consider the k-connected domination number γ _kc(G), the minimum cardinality of a dominating set S such that the induced subgraph G[S] is k-connected; cf. Shang et al. [575].

• 4. acyclic domination γ _a(G), minimum cardinality of a dominating set S such that the induced subgraph G[S] is acyclic. This was introduced by Hedetniemi, Hedetniemi, and Rall in 2000 [390], see also Goddard, Haynes and Knisley in 2004 [296].

• 5. capacity-k domination $\gamma _{cap_k}(G)$, minimum order of a vertex partition

  π = {V ₁, V ₂, …, V _k}, such that the subgraph induced by every set V _i has a spanning star of order at most k + 1, or equivalently, a dominating set S in which no vertex in S has to dominate more than k vertices in V − S; introduced by Goddard, Hedetniemi, Huff, and McRae in 2010 [300].

• 6. clique domination γ _K(G), minimum cardinality k of a dominating set S ⊆ V  such that G[S] ≃ K _k. Of course, such a dominating set might not exist for all graphs G, cf. Labendia and Canoy [473].

• 7. convex domination γ _conv(G). A set S ⊆ V  is called convex if for any two vertices u, v ∈ S, the vertices contained in all u − v geodesics belong to S. A set S is a convex dominating set if it is convex and dominating. The convex domination number γ _conv(G) equals the minimum cardinality of a convex dominating set in G. This was introduced by Lemańska in 2004 [479].

• 8. weakly convex domination γ _wcon(G). A set S ⊆ V  is called weakly convex if for any two vertices u, v ∈ S, there exists at least one u − v geodesic, all of whose vertices belong to S. A set S is a weakly convex dominating set if it is weakly convex and dominating. The weakly convex domination number γ _wcon(G) equals the minimum cardinality of a weakly convex dominating set in G; first appeared in a paper by Lemańska in 2004 [479].

• 9. cycle domination γ _cy(G), minimum cardinality of a dominating set S ⊆ V  such that G[S] has a Hamiltonian cycle. Such a dominating set might not exist for all graphs G. Harary and Nash-Williams have shown that the line graph L(G) of a graph G is Hamiltonian if and only if G contains a dominating cycle or G ≃ K _1,n, for n ≥ 3 [344].

• 10. equivalence domination γ _e(G), minimum cardinality of an equivalence dominating set. A set S is called an equivalence set if G[S] is a disjoint union of complete subgraphs; introduced by Arumugam and Sundarakannan in 2015 [21]. It is easy to see that equivalence domination generalizes 1-dependent domination, and therefore, for any graph G,

  $$\displaystyle \begin{aligned}\gamma(G) \leq \gamma_e(G) \leq \gamma_{[1]}(G) \leq i(G).\end{aligned}$$

• 11. forcing domination number F _γ(G). A subset T of a minimum dominating set S is a forcing subset for S if S is the unique minimum dominating set containing T. The forcing domination number F _γ(S) of S is the minimum cardinality among the forcing subsets of S, and the forcing domination number F _γ(G) of G is the minimum forcing domination number among the minimum dominating sets S of G. It follows from the definition that F _γ(G) ≤ γ(G). Chartrand et al. [123] show that for all integers 0 ≤ a ≤ b, with b positive, there exists a graph G with F _γ(G) = a and γ(G) = b.

• 12. geodetic domination γ _g(G). A geodetic set S is a set such that I[S] = ∪_{x,y ∈ S} I[x, y] = V , where the closed interval I[x, y] consists of x, y and all vertices lying on some x − y geodesic. A geodetic dominating set is both a geodetic set and a dominating set. In other words, S is a geodetic dominating set if every vertex in V − S lies on a shortest path between two vertices in S. The minimum cardinality of a geodetic dominating set of G is its geodetic domination number; introduced by Chartrand, Harary, and Zhang in 1999 [124]. See also Hansberg and Volkmann in [333] and Escuadro et al. in [237].

• 13. global domination γ _g(G), minimum cardinality of a set S such that S is a dominating set in G and S is also a dominating set in the complement $\overline {G}$ of G; introduced by Sampathkumar in 1989 [553]. The reader is referred to a chapter on global domination by Brigham and Carrington in 1998 [79], and a paper by Rall [533].

• 14. k-dependent domination γ _[k](G), minimum cardinality of a dominating set S such that for every vertex u ∈ S, |N(u) ∩ S|≤ k, that is, each vertex in S has at most k neighbors in S; first defined by Favaron et al. in 2002 [254]; see also Fink and Jacobson [263] and Samodivkin [552]. Notice that if S is a 1-dependent dominating set then the induced subgraph G[S] is a disjoint union of isolated vertices and K ₂s. Thus, for any graph G, γ(G) ≤ γ _[1](G) ≤ i(G).

• 15. paired domination γ _pr(G), minimum cardinality of a dominating set S such that the induced subgraph G[S] has a perfect matching; introduced by Haynes and Slater in 1995 [358] and [359]. We refer the reader to Desormeaux and Henning’s [193] survey on paired domination. See also Henning [407] for several conjectures related to paired and other variants of domination.

• 16. semipaired domination γ _pr(G), minimum cardinality of a semipaired dominating set, that is, a dominating set S for which the vertices in S can be partitioned into |S|∕2 pairs {u, v} such that d(u, v) ≤ 2; introduced by Haynes and Henning in 2018 [376].

• 17. semitotal domination γ _t2(G), minimum cardinality of a semitotal dominating set, that is, a dominating set such that every vertex u ∈ S is within distance 2 of a second vertex in S; introduced by Goddard, Henning, and McPillan in 2014 [302], but also defined in part by Hedetniemi et al. [395] in 2008.

3.8.2 Conditions on V (G) − S

• 1. α-domination γ _α(G), for 0 < α < 1, minimum cardinality of a set S such that for every vertex v ∈ V − S, |N(v) ∩ S|∕|N[v]|≥ α; introduced by Dunbar et al. in 2000 [214]. See also Gagarin et al. [275].

• 2. outer-connected domination $\gamma _{\overline {c}}(G)$, minimum cardinality of dominating set S such that the induced subgraph G[V − S] is connected; cf. Akhbari et al. [5].

• 3. b-disjunctive domination $\gamma ^d_b(G)$, minimum cardinality of a set S having the property that for every vertex u ∈ V − S, either u is adjacent to a vertex in S or there exist b vertices in S such that u is at distance 2 from each of these b vertices; introduced by Goddard, Henning, and McPillan in 2014 [301]. See also Henning and Marcon [410].

• 4. distance domination γ _≤k(G), minimum cardinality of a set S having the property that for every vertex u ∈ V − S there exists a vertex v ∈ S such that d(u, v) ≤ k; introduced by Slater in 1976 [585]. See Henning [403] for a comprehensive chapter of results on distance domination.

• 5. upper distance-k domination Γ _≤k(G), maximum cardinality of a minimal distance-k dominating set in G, that is, a dominating set S such that every vertex u ∈ V − S is within distance k of at least one vertex in S. The reader is referred to a chapter on distance domination by Henning in [403].

• 6. edge-cut domination $\gamma ^{\prime }_{ct}(G)$. An edge dominating set F ⊆ E of a graph G = (V, E) is an edge cut dominating set if the subgraph G[E − F] is disconnected. The edge cut domination number $\gamma ^{\prime }_{ct}(G)$ equals the minimum cardinality of an edge cut dominating set in G, cf. Fenstermacher et al. [258].

• 7. step domination γ _step(G). The k-neighborhood of a vertex v ∈ V  is the set N _=k(v) = {u ∈ V |d(u, v) = k}, of vertices whose distance from v is exactly k. A set S = {v ₁, v ₂, …, v _k} is called a step dominating set if there exists a set of k nonnegative integers i ₁, i ₂, …, i _k, such that $\pi = \{N_{=i_1}(v_1), N_{=i_2}(v_2), \ldots , N_{=i_k}(v_k)\}$ is a partition of V (G). The step domination number γ _step(G) equals the minimum cardinality of a step dominating set in G; introduced by Chartrand, Jacobson, Kubicka, and Kubicki in 1998 [120].

• 8. exact 2-step domination γ ₌₂(G). A set S ⊆ V  is called an exact 2-step dominating set if for every vertex v ∈ V , there exists a unique u ∈ S, such that d(u, v) = 2. The exact 2-step domination number γ ₌₂(G) equals the minimum cardinality of an exact 2-step dominating set in G; introduced by Chartrand, Harary, Hossain, and Schultz in 1995 [122]. See also Williams [639]. Note that exact 2-step dominating sets do not exist for all graphs.

• 9. downhill domination γ _dn(G), minimum cardinality of a downhill dominating set. A set S ⊆ V  is a downhill dominating set if every vertex v ∈ V  lies on some downhill path from a vertex in S. A path P = v ₁, v ₂, …, v _k is a downhill path if for every 1 ≤ i ≤ k − 1, deg(v _i) ≥ deg(v _i+1); introduced by Haynes, Hedetniemi, Jamieson, and Jamieson in 2014 [373]. See also Chen and Fujita [145].

• 10. edge domination γ′(G) and Γ′(G), minimum and maximum cardinalities of a minimal edge dominating set. The edge domination number and the independent edge domination number i′(G) were perhaps first discussed by Mitchell and Hedetniemi in 1977 [381], who showed that for trees T, γ′(T) = i′(T). It is clear that for any graph G, and its line graph L(G), γ′(G) = γ(L(G)). Since 1977, relatively little research has been done on the various types of edge domination in graphs. See, for example, Yannakakis and Gavril [642] and Chaemchen [105].

• 11. edge-vertex domination γ _ev(G), minimum cardinality of an ev-dominating set. A set M ⊆ E is an ev-dominating set if every vertex v ∈ V  is either incident to an edge in M or is adjacent to a vertex that is incident to an edge in M. This was introduced by Laskar and Peters in 1985 [477] and developed by Peters in his PhD thesis in 1986 [522]. See also the PhD thesis of Lewis [483]. This is closely related to vertex-edge domination γ _ve(G) defined below.

• 12. exponential domination γ _e(G), minimum cardinality of a set S having the property that for every vertex v ∈ V − S, w _s(v) ≥ 1, where

  $w_s(v) = \sum _{u \in S} \frac {1}{2^{\overline {d}(u,v) -1}}.$

  and $\overline {d}(u, v)$ equals the length of a shortest path in V − (S −{u}) if such a path exists, and ∞ otherwise; introduced by Dankelmann, Day, Erwin, Mukwembi, and Swart in 2009 [182].

• 13. inverse domination γ ⁻¹(G), minimum cardinality of a dominating set S ^∗ that is contained in the complement of a minimum dominating set of G; introduced by Kulli and Sigarkanti in 1991 [471]; cf. Domke et al. [200].

• 14. fair domination fd(G). A fair dominating set in a graph (or FD-set) is a dominating set S such that all vertices not in S are dominated by the same number of vertices in S; that is, every two vertices not in S have the same number of neighbors in S. The fair domination number fd(G) is the minimum cardinality of an FD-set; introduced by Caro, Hansberg, and Henning in 2012 [102].

• 15. k-domination γ _k(G), minimum cardinality of a dominating set S having the property that for every vertex v ∈ V − S, |N(v) ∩ S|≥ k; introduced by Fink and Jacobson in 1985 [263]. See also DaLaVina et al.[190] and Chellali et al. [138].

• 16. [1, k]-domination γ _[1,k](G). A subset S ⊆ V  is a [1, k]-(dominating) set if for every vertex v ∈ V − S, 1 ≤|N(v) ∩ S|≤ k; introduced by Chellali et al. in 2014 [140].

• 17. liars domination. Liar’s domination is about the detection of intruders in a graph G. We assume that an intruder can be located at any vertex v ∈ V . Intruders are detected by devices placed at various vertices, say u ∈ V , which can detect the presence and location of an intruder at any vertex in N[u]. A dominating set S can therefore detect and locate any intruder in a graph G. Liar’s domination considers the case of a single intruder in a graph, when a single detection device in S can fail, or lie. In this case, at least a double dominating set is required, but any triple dominating set will suffice. The reader is referred to the PhD Thesis of Roden Bowie in 2008 [72] and the papers by Roden and Slater [546] and Slater [588].

• 18. location domination γ _L(G), minimum cardinality of a dominating set S having the property that for no two vertices v, w ∈ V − S is N(v) ∩ S = N(w) ∩ S; introduced by Slater in 1975 [584]. See also Rall and Slater [534], Slater [587] and Exoo et al. [238]. The reader is also referred to a bibliography maintained by A. Lobstein, of more than 370 papers concerned with locating domination and its variations at: https://www.lri.fr/~lobstein/debutBIBidetlocdom.pdf.

• 19. mixed domination γ _m(G), minimum cardinality of a set S of vertices and edges such that every edge not in S is either adjacent to an edge in S or incident to a vertex in S, and every vertex not in S is either adjacent to a vertex in S or incident to an edge in S; introduced by Alavi, Behzad, Lesniak-Foster, and Nordhaus in 1977 [9], and later called mixed domination by Sampathkumar and Kamath in 1992 [554]. See also Zhao et al. [658].

• 20. P ₃ -domination $\gamma _{P_3}(G)$, minimum cardinality of P ₃-dominating set. A set S is P ₃ -dominating if every vertex v ∈ V − S forms a P ₃ with two vertices in S. This can happen in one of two ways: either v is dominated by two vertices in S, or v is dominated by a vertex u ∈ S that is adjacent to another vertex w ∈ S. Introduced by Haynes, Hedetniemi, Henning, and Slater in 2003 [366], who showed that for any graph G, $\gamma _{P_3}(G) \leq \{\gamma _t(G), \gamma _2(G) \}$, and that equality holds for any tree. This equality was later shown to hold for chordal graphs by Chellali and Favaron in [135].

• 21. power domination γ _P(G), minimum cardinality of power dominating set. A set S is a power dominating set if all vertices in V  are observed by vertices in S. A vertex observes itself and all of its neighbors, and if an observed vertex has all but one of its neighbors observed, then the remaining neighbor becomes observed; introduced by Haynes, Hedetniemi, Hedetniemi, and Henning in 2002 [364]. See also Guo, Niedermeier, and Raible [317] and generalizations to k-power domination, in which a vertex is observed if all but k of its neighbors have been observed. This was introduced by Chang et al. [111] and studied later by Dorbec and Klavžar [202].

• 22. restrained domination γ _r(G), minimum cardinality of a dominating set S such that every vertex in V − S has a neighbor in V − S; introduced by Domke, Hattingh, Hedetniemi, Laskar, and Markus in 1999 [198]. See also Henning [404] and Domke et al. [199]. See outer-connected domination.

• 23. secondary domination, γ _1,2(G) and γ _1,3(G), minimum cardinalities of a (1, 2) − and (1, 3)-dominating set, respectively. A set S is a (1, k)-dominating set if |S|≥ 2 and for every vertex v ∈ V − S there exists two vertices u ₁, u ₂ ∈ S such that d(v, u ₁) = 1 and d(v, u ₂) ≤ k. The following inequality chain exists for these parameters:

  $$\displaystyle \begin{aligned}\gamma(G) = \gamma_{1,4}(G) \leq \gamma_{1,3}(G) \leq \gamma_{1,2}(G) \leq \gamma_{1,1}(G) = \gamma_2(G).\end{aligned}$$

  This was introduced by Hedetniemi, Hedetniemi, Knisely, and Rall in 2008 [395]; see also Jamieson and Jamieson [433].

• 24. [1, 2]-domination γ _[1,2](G), minimum cardinality of a dominating set such that no vertex in V − S has more than two neighbors in S; introduced by Chellali, Haynes, Hedetniemi, and McRae in 2013 [139].

• 25. split domination γ _splt(G), minimum cardinality of a split dominating set in G. A dominating set S of vertices is called split dominating if the induced subgraph G[V − S] is either disconnected or K ₁; introduced by Kulli and Janakiram in 1997 [470].

• 26. vertex-edge domination γ _ve(G), minimum cardinality of a ve-dominating set. A set S ⊆ V  is a ve-dominating set if for every edge e = uv ∈ E, either u ∈ S, v ∈ S or there exists a vertex w ∈ S such that either uw ∈ E or vw ∈ E. This concept was first suggested by Alavi, Behzad, Lesniak-Foster and Nordhaus in 1977 [9], but was clarified and developed by Peters in his PhD thesis in 1986 [522], by Laskar and Peters in [477], and later by Lewis in his PhD thesis in 2007 [483]. In Lewis et al. [484] the following inequality chain is established.

  $$\displaystyle \begin{aligned}ir_{ve}(G) \leq \gamma_{ve}(G) \leq i_{ve}(G) \leq \alpha_{ve}(G) \leq \varGamma_{ve}(G) \leq IR_{ve}(G).\end{aligned}$$

  See also Boutrig et al. [69].

3.8.3 Conditions on (V (G), S)

• 1. cost effective domination γ _ce(G) and Γ _ce(G), minimum and maximum cardinalities of a dominating set that is cost effective. A vertex v ∈ S in a graph G = (V, E) is said to be cost effective if it is adjacent to at least as many vertices in V − S as it is in S. A dominating set S is cost effective if every vertex in S is cost effective. This idea originates in a paper by Aharoni, Milner, and Prikry in 1990 [4], and was later given the name cost effective domination by Haynes, Hedetniemi, Hedetniemi, McCoy, and Vasylieva in 2012 [372]; see also Haynes et al. [375].

• 2. very cost effective domination γ _vce(G) and Γ _vce(G), minimum and maximum cardinalities of a dominating set that is very cost effective. A vertex v ∈ S in a graph G = (V, E) is said to be very cost effective if it is adjacent to more vertices in V − S than it is in S. A dominating set S is very cost effective if every vertex in S is very cost effective; cf. Haynes et al. in 2012 [372] and [375].

• 3. detour domination γ _D(G). For a vertex v ∈ V , define D ⁻(v) = min{D(u, v) : u ∈ V −{v}}, where D(u, v) equals the maximum length of a u − v path in G. A vertex u is called a detour neighbor of v if D(u, v) = D ⁻(v). A vertex v is said to detour dominate a vertex u if u = v or u is a detour neighbor of v. A set S ⊂ V  is called a detour dominating set if every vertex in V  is detour dominated by some vertex in S. The detour domination number γ _D(G) of G equals the minimum cardinality of a detour dominating set in G; introduced by Chartrand, Haynes, Henning and Zhang in 2004 [128].

• 4. independent distance-k domination numbers i _≤k(G) and α _≤k(G), minimum and maximum cardinalities of a minimal independent distance-k dominating set in G; cf. Fricke, Hedetniemi, and Henning [270].

• 5. total distance domination $\gamma ^k_t(G)$. A set S of vertices is called a total distance-k dominating set if every vertex in V  is within distance k of a vertex in S. The total distance-k domination number $\gamma ^k_t(G)$ equals the minimum cardinality of a total distance-k dominating set; introducted by Henning, Oellermann, and Swart in 1995 [414].

• 6. weakly connected domination γ _w(G), minimum cardinality of a dominating set that is weakly connected. A set S is weakly connected if the graph with vertex set N[S] and all edges having at least one vertex in S is connected. This was introduced by Dunbar, Grossman, Hattingh, Hedetniemi, and McRae in 1995 [210]; see also Domke et al. [201] and Hattingh and Henning [352].

• 7. secure domination γ _s(G), minimum cardinality of a secure dominating set. A set S is a secure dominating set if for every vertex v ∈ V − S, there is an adjacent vertex u ∈ S such that the set S −{u}∪{v} is a dominating set; introduced by Cockayne, Favaron, and Mynhardt in 2003 [169]. See also Burger et al. [91].

• 8. eternal domination γ _∞(G), minimum cardinality of an eternally secure set in G. A set S of vertices is an eternal dominating set or eternally secure set if for all possible sequences of vertices u ₁, u ₂, …, there exists a sequence of dominating sets S = S ₁, S ₂, … and a sequence v ₁, v ₂, … such that for all i, S _i+1 = S _i −{v _i}∪{u _i}, where v _i ∈ S _i ∩ N[u _i]; introduced by Burger, Cockayne, Gründlingh, Mynhardt, van Vuuren, and Winterbach in 2004 [90], and further developed by Goddard, Hedetniemi and Hedetniemi in 2005 [297].

• 9. Hamiltonian domination γ _H(G). For vertices u, v ∈ V , let D(u, v) denote the length of a longest u − v path in G. For a vertex v, let D ⁺(v) = max{D(u, v) : u ∈ V −{v}}. A vertex u is called a Hamiltonian neighbor of v if D(u, v) = D ⁺(v). A vertex v is said to Hamiltonian dominate a vertex u if u = v or u is a Hamiltonian neighbor of v. A set S ⊆ V  is called a Hamiltonian dominating set if every vertex in V  is Hamiltonian dominated by some vertex in S. The Hamiltonian domination number γ _H(G) equals the minimum cardinality of a Hamiltonian dominating set in G; introduced by Chartrand et al. [129].

• 10. injective domination γ _in(G). The common neighborhood of two vertices u and v is the set N(u, v) = N(u) ∩ N(v). A set S ⊆ V  is called an injective dominating set if for every vertex v ∈ V − S there exists a vertex u ∈ S such that N(u, v) ≠ ∅. The injective domination number γ _in(G) equals the minimum cardinality of an injective dominating set in G; introduced by Alqesmah, Alwardi, and Rangarajan in 2018 [14].

• 11. k-tuple domination γ _×k(G), minimum cardinality of a dominating set S having the property that for every vertex v ∈ V , |N[v] ∩ S|≥ k; introduced by Harary and Haynes in 2000 [341].

• 12. k-emergency response number R _k(G), minimum cardinality of a k-emergency response set. A set S is a k-emergency response set if a set of responders stationed at the vertices in S can respond, by staying put or moving to a neighbor, to simultaneous emergencies at each vertex of any set A ⊆ V  of size at most k; introduced by Blair et al. in 2009 [55].

• 13. movable domination number $\gamma _m^1(G)$. A 1-movable dominating set is a dominating set S ⊂ V (G), having the property that for every v ∈ S, there exists a vertex u ∈ N(v) such that S −{v}∪{u} is a dominating set, capturing the idea that every vertex v in the dominating set can be replaced by a neighbor in N(v) and create another dominating set. The cardinality of a smallest movable dominating set of G is the 1-movable domination number $\gamma _m^1(G)$; introduced by Blair, Gera, and Horton in 2011 [56].

• 14. odd domination γ _odd(G), minimum cardinality of a dominating set having the property that for every vertex v ∈ V , |N[v] ∩ S| is an odd number. Odd domination and the fact that every graph G has an odd dominating set was introduced and proved by Sutner in 1989 [598]. See also Caro et al. [100] and Caro and Klostermeyer [98].

• 15. partial domination γ _p(G). Let p ∈ [0, 1]. A set S ⊆ V  is a p-dominating set if $\frac {|N[S]|}{|V|} \geq p$, that is, the set S dominates the fraction p of all vertices in G. The partial domination number γ _p(G) equals the minimum cardinality of a p-dominating set in G; introduced by Case et al. [103].

• 16. private domination Γ _pvt(G), maximum cardinality of a dominating set, every vertex in which has an external private neighbor, that is, for every vertex v ∈ S there exists a vertex w ∈ V − S for which N(w) ∩ S = {v}; equivalently, the maximum cardinality of an open irredundant dominating set. Notice that by definition, for any graph G, Γ _pvt(G) ≤{Γ(G), OIR(G)}; introduced by Hedetniemi, Hedetniemi, and Jacobs in 1990 [387]. See also Prasad et al. [524]. It should be noted that the minimum cardinality of a private dominating set of any isolate-free graph always equals the domination number γ(G).

• 17. stratified domination. A graph F is called 2-stratified if its vertices are partitioned into two non-empty sets, colored red and blue, but rooted at a given blue vertex v. A graph G is said to be F-colored if it is two-colored red and blue and every blue vertex v belongs to a copy of F rooted at v. The F-domination number of G is the minimum number of red vertices in an F-coloring of G. It can be seen that if F = K ₂ then F-domination is equal to normal domination in graphs. This concept was suggested by Rashidi in his PhD thesis in 1994 [536], and later developed by Chartrand et al. in 1995 [121], studied in Gera’s PhD thesis in 2005 [283], and by Haynes, Henning and Zhang in 2009 [370].

• 18. strong domination γ _s(G), minimum cardinality of a dominating set S having the property that for every vertex w ∈ V − S there exists a vertex v ∈ S such that v is adjacent to w and deg(v) ≥ deg(w), that is, every vertex w ∈ V − S is dominated by a vertex v ∈ S whose degree is greater than or equal to the degree of w; introduced by Sampathkumar and Pushpa Latha in 1996 [556].

• 19. weak domination γ _w(G), minimum cardinality of a dominating set S having the property that for every vertex w ∈ V − S there exists a vertex v ∈ S such that v is adjacent to w and deg(v) ≤ deg(w), that is, every vertex w ∈ V − S is dominated by a vertex v ∈ S whose degree is less than or equal to the degree of w; introduced by Sampathkumar and Pushpa Latha in 1996 [556].

3.9 Dominating Function Numbers

All of the parameters in this subsection consider vertex labelings of the form f : V → X where X is a finite set of integers, and the function satisfies the general condition that for every vertex v ∈ V , ∑_{u ∈ N[v]} f(u) ≥ 1. Unless otherwise stated, the weight of a function f is Σ _{v ∈ V} f(v).

• 1. broadcast domination γ _b(G) and Γ _b(G), minimum and maximum weights, respectively, of a minimal function f : V →{0, 1, 2, …, diam(G)}, such that for every vertex v ∈ V , with f(v) = 0, there exists a vertex u ∈ V  such that f(u) ≥ d(u, v). In this case, we say that vertex v hears a broadcast from vertex u, or in general, a vertex v hears a broadcast from a vertex u if f(u) ≥ d(u, v). Such a function is called a dominating broadcast.

  $$\displaystyle \begin{aligned}\gamma_b(G) \leq min\{\gamma(G), rad(G)\} \leq max\{\varGamma(G), diam(G)\} \leq \varGamma_b(G).\end{aligned}$$

  This was introduced by Erwin in 2004 [236]. See Dunbar et al. [215], Bresar and Spacapan [75], and Dabney et al. [179].

  Also defined in these papers are: p _b(G) and P _b(G), the broadcast packing numbers [in a packing broadcast no vertex in the set hears two or more broadcasts], the broadcast independence numbers i _b(G) and α _b(G) [in an independent broadcast no vertex with f(v) > 0 hears another broadcast], and Γ _ib(G) and Γ _eb(G), the maximum weights of a minimal independent and dominating broadcast [every vertex hears at least one broadcast] and an efficient dominating broadcast [every vertex hears exactly one broadcast]. It is noteworthy that a minimum weight dominating broadcast can always be achieved with an efficient broadcast, and consequently the problem of computing the broadcast domination number γ _b(G) of any graph can be computed in polynomial time, cf. Heggernes and Lokshtanov [400].

• 2. fractional domination γ _f(G), minimum weight of a function f : V → [0, 1] such that for every vertex v ∈ V , ∑_{u ∈ N[v]} f(u) ≥ 1; introduced by Hedetniemi, Hedetniemi, and Wimer in 1987 [384]. See also the PhD thesis by Rubalcaba in 2005 [548].

• 3. {k}-domination γ _{k}(G), minimum weight of a function f : V →{0, 1, 2, …, k} such that for every vertex v ∈ V , Σ _{u ∈ N[v]} f(u) ≥ k; introduced by Domke et al. in 1991 [197]. See also Hou and Lu [424].

• 4. majority domination γ _maj(G), minimum weight of a function f : V →{−1, 0, 1} such that for at least half of the vertices v ∈ V , f(N[v]) ≥ 1; introduced by Broere, Hattingh, Henning, and McRae in 1995 [82]. See also a chapter on majority domination by Hattingh in 1998 [351], and papers by Yeh and Chang [644] and Holm [418].

• 5. minus domination γ ⁻(G), minimum weight of a function f : V →{−1, 0, 1} such that for every vertex v ∈ V , f(N[v]) ≥ 1; introduced by Dunbar, Hedetniemi, Henning, and McRae in 1999 [212]. See also Dunbar et al. [209] and [208] and Zelinka [655].

• 6. k-rainbow domination γ _rk(G), minimum weight of a function that assigns to each vertex a subset of colors chosen from the set {1, 2, …, k}, that is, $f:V(G)\rightarrow \mathcal {P(}\{1,2, \ldots , k\})$, such that for every vertex v ∈ V  with f(v) = ∅, ⋃_{u ∈ N(v)} f(u) = {1, 2, …, k}. Such a function f is called a k-rainbow dominating function (kRDF) of G; introduced by Brešar and Kraner in 2007 [76] and in 2008 by Brešar, Henning and Rall in 2008 [77].

• 7. signed domination γ ^±(G), minimum weight of a function f : V →{−1, 1} such that for every vertex v ∈ V , f(N[v]) ≥ 1; introduced by Dunbar, Hedetniemi, Henning, and Slater in 1995 [207]. See also Haas and Wexler [323], Chen and Song [146] and Hosseini Moghaddam, Khodkar, and Samadi [508].

• 8. Roman domination γ _R(G), minimum weight of a function f : V →{0, 1, 2} such that every vertex u ∈ V , with f(u) = 0 is adjacent to a vertex v ∈ V  with f(v) = 2; introduced by Cockayne, Dreyer, Hedetniemi, and Hedetniemi in 2004 [170]. Since its introduction in 2004, many varieties of Roman domination (RD) have appeared, too numerous to define all here. We define a few varieties below.

• 9. weak Roman domination γ _r(G), minimum weight of a function f : V →{0, 1, 2} such that every vertex u with f(u) = 0 is adjacent to a vertex v with f(v) > 0, and the function f′ obtained from f by setting f′(u) = 1, f′(v) = f(v) − 1, and f′(w) = f(w), for all w ∈ V −{u, v} has no vertex x with f′(x) = 0 and all neighbors y ∈ N(x) have f′(y) = 0; introduced by Henning and Hedetniemi in 2001 [408].

• 10. Roman {2}-domination γ _R2(G), minimum weight of a function f : V →{0, 1, 2} such that for every vertex v ∈ V  with f(v) = 0, either v is adjacent to a vertex w with f(w) = 2 or v is adjacent to two vertices x, y with f(x) = f(y) = 1; introduced by Chellali, Haynes, Hedetniemi, and McRae in 2016 [141], but is called Italian domination in [409].

• 11. double Roman domination γ _dR(G), minimum weight of a function f : V (G) →{0, 1, 2, 3} satisfying the following conditions. For i ∈{0, 1, 2, 3}, let V _i = {v ∈ V (G)|f(v) = i}. (1) if f(v) = 0, then vertex v must have at least two neighbors in V ₂ or one neighbor in V ₃. (2) if f(v) = 1, then v must have at least one neighbor in V ₂ ∪ V ₃; introduced by Beeler, Haynes, and Hedetniemi in 2016 [38].

• 12. Roman k-domination γ _kR(G), minimum weight of a function f : V →{0, 1, 2} such that every vertex v for which f(v) = 0 is adjacent to at least k vertices v ₁, v ₂, …, v _k, where f(v _i) = 2 for 1 ≤ i ≤ k; defined by Hansberg and Volkmann in 2009 [332].

• 13. independent Roman domination i _R(G), minimum weight of a Roman dominating function f for which the set of vertices assigned positive values under f is independent; defined by Cockayne, Dreyer, Hedetniemi and Hedetniemi in 2004 [170].

• 14. edge Roman domination $\gamma ^{\prime }_R(G)$, minimum weight of a function f : E(G) →{0, 1, 2} such that every edge e with f(e) = 0 is adjacent to some edge e′ with f(e′) = 2; introduced by Pushpam and Mai in 2009 [528]. See also Chang et al. [112].

• 15. signed Roman domination γ _sR(G), minimum weight of a function f : V →{−1, 1, 2} such that for every vertex v ∈ V , (1) f(N[v]) ≥ 1, and (2) if f(v) = −1 then v must have a neighbor w with f(w) = 2; introduced by Ahangar, Henning, Löwenstein, Zhao, and Samodivkin in 2014 [2]. See also Haas and Wexler [323], Chen and Song [146] and Hosseini Maghaddam et al. [508].

• 16. total Roman domination γ _tR(G), minimum weight of a Roman dominating function with the additional property that the subgraph of G induced by the set of all vertices assigned positive values under f has no isolated vertices; introduced by Liu and Chang in 2013 [488]. See also Ahangar, Henning, Samodivkin, and Yero in 2016 [3].

3.10 Domatic Numbers

In its most general form, a domatic number is the maximum order k of a vertex partition π = {V ₁, V ₂, …, V _k}, such that each set V _i is a given type of dominating set. Thus, there are as many types of domatic numbers as there are types of dominating sets. In this subsection, we define only nine of the many types of domatic numbers that have been studied. For more on domatic numbers, see the chapter by Zelinka in [654].

• 1. domatic number d(G), maximum order of a partition of V (G) into dominating sets; introduced by Cockayne and Hedetniemi in 1975 [161].

• 2. total domatic number d _t(G), maximum order of a partition of V (G) into total dominating sets; introduced by Zelinka in 1989 [653].

• 3. connected domatic number d _c(G), maximum order of a partition of V (G) into connected dominating sets; introduced by Zelinka in 1986 [652].

• 4. paired domatic number d _pr(G), maximum order of a partition of V (G) into paired dominating sets; introduced by Haynes and Slater in 1995 [358].

• 5. k-domatic number d _k(G), maximum order of a partition of V (G) into distance-k dominating sets; introduced by Zelinka in 1983 [651].

• 6. edge-domatic number ed(G), maximum order of a partition of E(G) into edge dominating sets; introduced by Zelinka in 1983 [650]. The edge-domatic number of G is the domatic number of the line graph of G.

• 7. signed domatic number d _S(G), maximum number of functions in a signed dominating family (of functions) of G; introduced by Volkmann and Zelinka in 2005 [629]. A set {f ₁, f ₂, …, f _d} of signed dominating functions on G with the property that $\displaystyle \sum _{i=1}^d f_i(v) \le 1$ for each v ∈ V (G) is called a signed dominating family (of functions) on G.

• 8. Roman domatic number d _R(G), maximum number of functions in a Roman dominating family (of functions) of G; introduced by Sheikholeslami and Volkmann in 2010 [578]. A set {f ₁, f ₂, …, f _d} of Roman dominating functions on G with the property that $\displaystyle \sum _{i=1}^d f_i(v) \le 2$ for each v ∈ V (G) is called a Roman dominating family (of functions) on G.

• 9. fractional domatic number FD(G). A thoroughly distributed dominating family ${\mathcal {F}}_{\mathrm {dom}}$ of a graph G is a family of (not necessarily distinct) dominating sets of G. Let $d_{\mathcal {F}}$ denote the maximum times any vertex of G appears in ${\mathcal {F}}_{\mathrm {dom}}$, and define the effective ratio of the family ${\mathcal {F}}_{\mathrm {dom}}$ as the ratio of the number of sets in ${\mathcal {F}}_{\mathrm {dom}}$ to $d_{\mathcal {F}}$. The fractional domatic number FD(G) is defined as the supremum of the effective ratio taken over all thoroughly distributed dominating families. That is,

  $$\displaystyle \begin{aligned} FD(G) = \sup_{{\mathcal{F}}_{\mathrm{dom}}} \, \frac{ |{\mathcal{F}}_{\mathrm{dom}}| }{ d_{\mathcal{F}} }. \end{aligned}$$

  The fractional domatic number was introduced in 1990 by Rall [532].

  The fractional total domatic number is defined analogously. The fractional total domatic number was introduced by Goddard and Henning [295], and studied further, for example, by Abbas et al. [1] and Henning and Yeo [412].

3.11 Domination and Coloring Related Numbers

In this subsection we list a variety of parameters having some relationships with coloring or domination in graphs.

• 1. annihilation number a(G), maximum integer k such that the sum of the first k terms of the non-decreasing degree sequence of G is at most the size m = |E| of G. This was introduced and studied by Pepper in 2009 [521]. Desormeaux, Haynes, and Henning in 2013 [194] showed that for the total domination number of any tree T, γ _t(T) ≤ a(T) + 1; Dehgardi, Norouzian, and Sheikholeslami in 2013 [187] showed that for the domination number, γ(T) ≤ (3a(T) + 2)∕4; Dehgardi, Sheikholeslami and Khodkar in 2014 [188], showed that for the paired domination number, $\gamma _{pr}(T) \leq \frac {4a(T)+2}{3}$; Desormeaux, Henning, Rall and Yeo in 2014 [195] showed that for the 2-domination number of trees T, γ ₂(T) ≤ a(T) + 1; and Amjadi in 2015 [16], showed that for the double domination number, $\gamma _{\times 2}(T) \leq \frac {3a(T)+1}{2}$.

• 2. acquisition number a(G). To a connected graph G, assign the value 1 to all vertices, that is, let f(v) = 1 for all v ∈ V . An acquisition is the process of selecting two adjacent vertices u and v where f(u) ≥ f(v) > 0, and redefining f(u) = f(u) + f(v) and f(v) = 0. This process continues until no more acquisitions are possible. The acquisition number a(G) is the minimum possible number of vertices having a nonzero value at the end of an acquisition sequence. Note that if S is the set of vertices having nonzero value at the end of an acquisition sequences, then S is an independent set. This parameter was introduced in 1995 by Lampert and Slater [476] and further studied by Slater and Wang [589].

• 3. R-annihilated number ra(G). For a vertex u ∈ S, whose set of private neighbors pn[u, S] with respect to S is nonempty, a vertex v ∈ V − S is said to annihilate u if v is adjacent to every vertex in pn[u, S]. This means that u has a private neighbor with respect to the set S but does not have a private neighbor with respect to the set S ∪{v}. Let R = V − N[S] denote the subset of V  not dominated by S. Then S is said to be R-annihilated, or an Ra-set, if every vertex in R annihilates some vertex in S. This is the property satisfied by every maximal irredundant set. The minimum cardinality of an Ra-set is denoted by ra(G); introduced by Cockayne, Favaron, Puech and Mynhardt in 1998 [167], and further studied by Puech in 2000 [525].

• 4. bondage number b(G), minimum number of edges that can be deleted from G in order to increase the domination number. This parameter was introduced by Fink, Jacobson, Kinch, and Roberts in 1990 [265], and further studied by Hartnell and Rall in 1994 [350], and Wang in 1996 [636].

• 5. cost effective numbers ce(G) and CE(G), minimum and maximum cardinalities of a maximal cost effective set. A set S is cost effective if for every vertex u ∈ S, |N(u) ∩ (V − S)|≥|N(u) ∩ S|, introduced by Chellali, Haynes, and Hedetniemi in 2017 [142].

• 6. very cost effective numbers vce(G) and V CE(G), minimum and maximum cardinalities of a maximal very cost effective set. A set S is very cost effective if for every vertex u ∈ S, |N(u) ∩ (V − S)| > |N(u) ∩ S|; introduced by Chellali et al. in 2017 [142].

• 7. differential number ∂(G), maximum value of |B(S)|−|S|, for a set S ⊆ V , where B(S) = N[S] − S. Note that for any isolate-free graph G,

  $$\displaystyle \begin{aligned}n - 2\gamma(G) \leq \partial(G) \leq n - \gamma(G) -1 = \varPsi(G) - 1.\end{aligned}$$

  This was introduced by Mashburn, Haynes, Hedetniemi, Hedetniemi, and Slater in 2006 [499]; see also Haynes et al. [374].

• 8. domination equivalence numbers de(G) and DE(G), minimum and maximum number of vertices in a domination equivalent pair. A set S of vertices has a domination equivalent if there exists a set R ⊆ V − S such that N[S] = N[R]. Similarly, one can define the open domination equivalence numbers, ode(G) and ODE(G), in terms of two disjoint sets S and R such that N(S) = N(R). Note that it is easy to see that for any graph G of order n, de(G) ≤ γ(G), and DE(G) = n − γ(G); introduced by Blair, Goddard, Hedetniemi, Hedetniemi, and Horton in 2005 [53].

• 9. domination subdivision number sd _γ(G), minimum number of edges which when subdivided once increase the domination number. This concept is due to Arumugam, but was first defined and studied by Haynes, Hedetniemi and Hedetniemi in 2000 [362]. See also Haynes et al. in 2001 [363] where it is shown that for any connected graph of order n ≥ 3, sd _γ(G) ≤ γ(G) + 1.

  A large number of variants of the domination subdivision number have been studied since this parameter was introduced, including connected domination, double domination, independent domination, convex domination, weakly convex domination, rainbow domination, game total domination, restrained domination, doubly connected, and Roman domination subdivision numbers, which are too numerous to discuss here. We mention only the following two variants.

• 10. total domination subdivision number $sd_{\gamma _t}(G)$, minimum number of edges which when subdivided once increase the total domination number; introduced by Haynes, Hedetniemi, and van der Merwe in 2003 [367]. See also Haynes et al. [368].

• 11. paired domination subdivision number $sd_{\gamma _{pr}}(G)$, minimum number of edges which when subdivided once increase the paired domination number; introduced by Favaron, Karami, and Sheikholeslami in 2009 [256].

• 12. efficiency of a graph ε(G). The efficiency of a set S ⊆ V  is defined as ε(S) = |{v ∈ V − S : |N(v) ∩ S| = 1}|, that is, the efficiency of a set S equals the number of vertices in V − S that are adjacent to exactly one vertex in S. The efficiency of a graph ε(G) equals the maximum efficiency of a set S ⊆ V , that is, the maximum number of vertices that can be dominated exactly once by a set S; introduced by Bernhard, Hedetniemi, and Jacobs in 1993 [47]. See also Blair [52], Telle and Proskurowski [603] and Hedetniemi et al. [396].

• 13. hub number hub(G). A vertex set S having the property that for every u, v ∈ V − S, there exists a u − v path, every internal vertex of which belongs to S is called a hub set. The hub number of a graph G equals the minimum cardinality of a hub set in G; introduced as the hub number by Walsh in 2006 [634], and later studied by Grauman et al. [311], who showed that

  $$\displaystyle \begin{aligned}h(G) \leq h_c(G) \leq \gamma_c(G) \leq h(G) + 1,\end{aligned}$$

  where h _c(G), the connected hub number, equals the minimum cardinality of a hub set S for which the induced subgraph G[S] is connected, and γ _c(G) equals the connected domination number of G.

  However, the original idea seems to be due to Newman-Wolfe, Dutton, and Brigham in 1988 [514], who gave the following definitions. A subset S is a strong connecting set (SCS) if every pair of vertices not in S has a connecting path through S. Similarly, S is a weak connecting set (WCS) if every pair of nonadjacent vertices not in S has a connecting path through S. The minimum cardinality of an SCS (resp. WCS) equals the strong connection number γ _s(G) (resp.weak connection number γ _w(G)). They show that for any connected graph G,

  $$\displaystyle \begin{aligned}\gamma_w(G) \leq \gamma_s(G) \leq \gamma_c(G)_ \leq \gamma_w(G) + 1.\end{aligned}$$

  See also Johnson, Slater, and Walsh [436].

• 14. iterated independence numbers i ^∗(G) and α ^∗(G), minimum and maximum number of iterations possible in a process of iteratively removing from G a maximal independent set. It can be seen that i ^∗(G) = χ(G) and α ^∗(G) = Γr(G), the Grundy number of G.

• 15. iterated domination numbers γ ^∗(G) and Γ ^∗(G), minimum and maximum number of iterations possible in a process of iteratively removing from G a minimal dominating set.

• 16. iterated irredundance numbers ir ^∗(G) and IR ^∗(G), minimum and maximum number of iterations possible in a process of iteratively removing from G a maximal irredundant set.

  All of these iterated numbers were introduced by Hedetniemi, Hedetniemi, McRae, Parks, and Telle in 2004 [392], who observed that for any graph G,

  $$\displaystyle \begin{aligned}ir^*(G) \leq \gamma^*(G) \leq i^*(G) = \chi(G) \leq \alpha^*(G) \leq \varGamma^*(G) \leq IR^*(G).\end{aligned}$$

  It remains an open problem to show, without appealing to the Four Color Theorem, that for any planar graph G, ir ^∗(G) ≤ 4 and γ ^∗(G) ≤ 4.

• 17. neighborhood numbers n(G) and N(G), minimum and maximum cardinalities of a minimal neighborhood set, that is, a set S such that ⋃_{u ∈ S} G[N[u]] = G; introduced by Sampathkumar and Neeralagi in 1986 [557]. See also Brigham and Dutton [80] and Chang et al. [109].

• 18. reinforcement number r(G), minimum number of edges that have to be added to G so that in the resulting graph G′, γ(G′) < γ(G); introduced by Kok and Mynhardt in 1990 [459]. See also Blair et al. [54].

3.12 Alliance Numbers

The concepts related to an alliance in a graph G were introduced by Kristiansen, Hedetniemi, and Hedetniemi in 2004 [391]. Since then more than 100 papers have been written about these types of sets of vertices in a graph. The reader is referred to a recent, extensive survey on alliances in graphs by González Yero and Ridríguez-Velázquez [646].

• 1. defensive alliance number a(G), minimum cardinality of a set S having the property that for every vertex u ∈ S, |N[u] ∩ S|≥|N(u) ∩ (V − S)|; introduced by Kristiansen, Hedetniemi, and Hedetniemi in 2004 [391]. See also Fricke et al. [272] and Sigarreta and Rodriguez [580].

• 2. offensive alliance number a ₀(G), minimum cardinality of a set S having the property that for every vertex v ∈ (V − S) ∩ N(S), |N(v) ∩ S|≥|N[v] ∩ (V − S)|; introduced by Kristiansen et al. [391]. See also Chellali [134] and Rodriguez and Sigarreta [547].

• 3. powerful alliance number a _p(G), minimum cardinality of a set S that is both a defensive alliance and an offensive alliance; introduced by Brigham, Dutton, Haynes, and Hedetniemi in 2009 [81].

• 4. global defensive alliance number γ _a(G), minimum cardinality of a defensive alliance S that is also a dominating set, that is, every vertex v ∈ V − S is adjacent to at least one vertex in the defensive alliance S; introduced by Haynes, Hedetniemi, and Henning in 2003 [365]. See also Favaron in [250] and Bouzefrane, Chellali, and Haynes in [71].

• 5. global offensive alliance number $\gamma _{a_o}(G)$, minimum cardinality of an offensive alliance that is also a dominating set, that is, every vertex v ∈ V − S is adjacent to at least one vertex in the offensive alliance S; introduced by Sigarreta and Rodriguez in 2009 [581] and Bouzefrane and Chellali [70]. See also Chellali and Volkmann [137].

• 6. global powerful alliance number $\gamma _{a_p}(G)$, minimum cardinality of a powerful alliance that is also a dominating set, that is, every vertex v ∈ V − S is adjacent to at least one vertex in the powerful alliance S.

• 7. defensive alliance partition number ψ _a(G), maximum order k of a partition π = {V ₁, V ₂, …, V _k}, such that each set V _i is a defensive alliance. This idea seems to have originated in a paper by Gerber and Kobler in 2000 [288], was studied by Shafique and Dutton in 2002 [570], and further studied by Haynes and Lachniet in [357], and Eroh and Gera in [234, 235].

• 8. distribution center number dc(G), minimum cardinality of a distribution center of a graph G. A non-empty set of vertices S ⊆ V  is a distribution center if every vertex v ∈ (V − S) ∩ N(S) is adjacent to a vertex u ∈ S with |N[u] ∩ S|≥|N[v] ∩ (V ∖ S)|; introduced by Desormeaux et al in 2018 [196].

3.13 Irredundance Numbers

The concept of an irredundant set in a graph is a natural consequence of the property of being a minimal dominating set. If S is a minimal dominating set, then for every vertex v ∈ S, the subset S −{v} is no longer a dominating set. This means that every vertex v ∈ S must either (i) dominate some vertex in V − S that no vertex in S −{v} dominates, or (ii) no vertex in S −{v} dominates v. Any set S in which every vertex v satisfies condition (i) or (ii) is an irredundant set; note that the set S itself need not be a dominating set. From this one observation, all of the types of irredundant sets defined in this subsection naturally arise. A very comprehensive and in-depth study of the concept of irredundance in graphs can be found in the Ph.D. thesis of Finbow [262].

• 1. irredundance numbers ir(G) and IR(G), minimum and maximum cardinalities of a maximal irredundant set. A set S is an irredundant set if for every vertex v ∈ S, pn[v] = N[v] − N[S −{v}] ≠ ∅. The set pn[v] is called the set of private neighbors of v with respect to the set S. If v ∈ pn[v], then v is not adjacent to any vertex in S −{v} and v is said to be its own private neighbor. Every vertex w ∈ V − S for which w ∈ pn[v] is called an external private neighbor of v. It is worth noting that every minimal dominating set is an irredundant set. Irredundant sets were first defined and studied by Cockayne, Hedetniemi and Miller in 1978 [162]. See also early survey paper by Hedetniemi et al. [383], and a comprehensive paper showing the full generality of irredundance in graphs by Cockayne and Finbow [160]. In [386], Hedetniemi, Jacobs and Laskar show that IR(G) = p′(G) ≤ r(N(G)), where p′(G) equals the maximum integer k such that the closed neighborhood matrix contains a k × k permutation submatrix, and r(N(G)) equals the rank of the neighborhood matrix.

• 2. open irredundance oir(G) and OIR(G), minimum and maximum cardinalities of a maximal open irredundant set in G. A set S is open irredundant if every vertex u ∈ S has an external private neighbor; first studied by Farley and Schacham in 1983 [245]; see also Farley and Proskurowski [244], Cockayne et al. [171], and Cockayne [159].

• 3. open irredundance ooir(G) and OOIR(G), minimum and maximum cardinalities of a maximal open irredundant set in G. A set S is open irredundant if every vertex u ∈ S has an external or internal private neighbor. An internal private neighbor of a vertex u ∈ S is a vertex v ∈ S whose only neighbor in S is u; introduced by Cockayne, Finbow, and Swarts in 2010 [172]. In [386] Hedetniemi, Jacobs and Laskar show that OOIR(G) = p(G) ≤ r(G), where p(G) equals the maximum integer k such that the adjacency matrix contains a k × k permutation submatrix and r(G) denotes the rank of G, i.e. dimension of the row space of the adjacency matrix A(G) of G.

• 4. closed open irredundance coir(G) and COIR(G), minimum and maximum cardinalities of a maximal closed open irredundant set in G. A set S is closed open irredundant if every vertex u ∈ S has either itself as a private neighbor, an external private neighbor or an internal private neighbor.

• 5. total irredundance ir _t(G) and IR _t(G), minimum and maximum cardinalities of a maximal total irredundant set. A set S is a total irredundant if and only if for every vertex v ∈ V , N[v] − N[S −{v}] ≠ ∅; introduced by Favaron, Haynes, Hedetniemi, Henning, and Knisley in 2002 [253]. See also Hedetniemi, Hedetniemi, and Jacobs [388].

• 6. co-irredundance, cir(G) and CIR(G), the minimum and maximum cardinalities of a minimal co-irredundant set. A set S is a co-irredundant set if and only if the complement V − S is an irredundant set; introduced by Arumugam, Hedetniemi, Hedetniemi, Sathikala, and Sudha in 2015 [26], who showed the following:

  $$\displaystyle \begin{aligned}ir(G) \leq \gamma(G) \leq cir(G) \leq \psi(G) \leq \beta(G) \leq \beta^+(G) \leq \varPsi(G) \leq CIR(G).\end{aligned}$$
  $$\displaystyle \begin{aligned}CIR(G) \geq \varPsi(G) \geq IR(G) \geq \varGamma(G) \geq \alpha(G) \geq i(G) \geq \gamma(G) \geq ir(G).\end{aligned}$$

• 7. external redundance er(G) and ER(G), minimum and maximum cardinalities of a minimal external redundant set. A set S is external redundant if for all vertices v ∈ V − S, there exists a vertex w ∈ S ∪{v} such that pn[w, S ∪{v}] = ∅, and if w ∈ S then pn[w, S] ≠ ∅. An equivalent definition of external redundance is the following. For any set S of vertices, define the private neighbor count pnc(S) to equal the number of vertices in S that have a private neighbor. A set S is pnc-maximal if for every vertex v ∈ V − S, pnc(S ∪{v}) ≤ pnc(S). It can be seen that er(G) and ER(G) equal the minimum and maximum cardinalities of a pnc-maximal set in G. Note that:

  $$\displaystyle \begin{aligned}er(G) \leq ir(G) \leq \gamma(G) \leq i(G) \leq \alpha(G) \leq \varGamma(G) \leq IR(G) \leq ER(G).\end{aligned}$$

  External redundance was introduced by Cockayne, Hattingh, Hedetniemi, Hedetniemi, and McRae in 1997 [166]; see also Goddard and Hedetniemi [294].

  Arumugam et al. [26] have combined many of the domination and irredundance parameters into the following inequalities and equalities, which they have called the Extended Domination Chain, and the Extended Covering Chain, respectively.

  $$\displaystyle \begin{aligned} \begin{array}{cccccccc} ir(G)&\leq\gamma(G)&\leq i(G)&\leq\alpha(G)&\leq\varGamma(G)&\leq IR(G)&\leq\varPsi(G)&\leq\ CIR(G) \\ + & + & + & + & + & + & + & + \\ CIR(G)& \geq \varPsi(G) & \geq \varLambda(G) & \geq \beta(G) & \geq \psi(G) & \geq \ cir(G) & \geq \gamma(G) & \geq ir(G) \\ = & = & = & = & = & = & = & = \\ n & n & n & n & n & n & n & n \\ \end{array} \end{aligned}$$

  They also added the following interesting comparison of two inequality chains:

  $$\displaystyle \begin{aligned} \begin{array}{cccccc} \gamma(G) & \leq \ i(G) & \leq \alpha(G) & \leq \varGamma(G) & \leq \ IR(G) & \leq \varPsi(G) \\ \gamma(G) & \leq \ cir(G) & \leq \psi(G) & \leq \beta(G) & \leq \varLambda(G) & \leq \varPsi(G) \\ \end{array} \end{aligned}$$

3.14 Perfect, Nearly Perfect, and Almost Perfect Numbers

A vertex v in a set S ⊆ V  is called S-perfect if |N[v] ∩ S| = 1, that is, the closed neighborhood N[v] contains exactly one vertex in S.

A vertex v in a set S ⊆ V  is called almost S-perfect if it is either S-perfect or is adjacent to an S-perfect vertex.

When we say more simply that a vertex is perfect or almost perfect it is always with reference to some given set S.

• 1. perfect set numbers θ _p(G) and Θ _p(G). A set S ⊆ V  is perfect if every vertex v ∈ S is perfect. It is easy to show that a set S is perfect if and only if it is independent. Thus, the minimum cardinality of a maximally perfect set θ _p(G) = i(G), the independent domination number i(G), while the maximum cardinality of a perfect set Θ _p(G) = α(G), the vertex independence number.

• 2. semi-perfect code, perfect domination,or externally perfect sets γ _p(G) and Γ _p(G), minimum and maximum cardinalities of a perfect dominating set. A (dominating) set S is perfect if every vertex v ∈ V − S is adjacent to exactly one vertex in S. Note that for the 2 × 3 grid graph , γ _p(G) = 2 while Γ _p(G) = 3; introduced by Fellows and Hoover in 1991 [257]. See also Cockayne et al. [165], Chang et al. [110] and Yen and Lee [645].

• 3. almost perfect set numbers θ _ap(G) and Θ _ap(G). A set S is almost perfect if every vertex v ∈ S is almost perfect; for brevity, we say that an almost perfect set is an ap set. The minimum cardinality of a maximal ap set is θ _ap(G), and the maximum cardinality of an ap set is Θ _ap(G); introduced by Hedetniemi, Hedetniemi, and Hedetniemi in 2004 [397], where it is shown that for any graph G, θ _ap(G) = ir(G) and Θ _ap(G) = IR(G).

• 4. externally almost perfect set numbers θ ^eap(G) and Θ ^eap(G), minimum and maximum cardinalities of a minimal eap set in G. A set S is externally almost perfect if every vertex u ∈ V − S is either perfect or adjacent to a perfect vertex; for brevity, we say that an externally almost perfect set is an eap set; cf. [397].

• 5. completely almost perfect set numbers or perfect neighborhood numbers θ(G) and Θ(G). A set S is completely almost perfect if every vertex v ∈ V  is either perfect or is adjacent to a perfect vertex. Completely almost perfect sets are called perfect neighborhood sets in the literature. Let θ(G) and Θ(G) equal the minimum and maximum cardinalities of a perfect neighborhood set in G. This concept was introduced by Fricke, Haynes, Hedetniemi, Hedetniemi, and Henning in 1999 [271], who showed that for any graph G, Θ(G) = Γ(G); see also Cockayne et al. [168], Favaron and Puech [252], Fricke et al. [271] and Hedetniemi et al. [389].

• 6. perfect codes, efficient domination, completely perfect sets or perfect total domination γ _P(G), minimum cardinality of a set S ⊆ V  having the property that for every vertex v ∈ V , |S ∩ N[v]| = 1. Equivalently, a perfect code consists of a set S = {v ₁, v ₂, …, v _k}⊆ V  having the property that V = {N[v ₁], N[v ₂], …, N[v _k]} is a partition of V (G). It is important to point out that not every graph has a perfect code or efficient dominating set, for example, the cycle C ₅; introduced by Biggs in 1973 [51]. See also the survey of varieties of perfect codes by Klostermeyer [457].

• 7. nearly perfect numbers n _p(G) and N _p(G). A set S is perfect if every vertex in V − S is adjacent to exactly one vertex in S. A set S of vertices is nearly perfect if every vertex in V − S is adjacent to at most one vertex in S. Nearly perfect sets are closely related to 2-packings of graphs, strongly stable sets, dominating sets and efficient dominating sets. A nearly perfect set S is 1-minimal if for every vertex u ∈ S, the set S −{u} is not nearly perfect. Similarly, a nearly perfect set S is 1-maximal if for every vertex u ∈ V − S, S ∪{u} is not nearly perfect. Let n _p(G) equal the minimum cardinality of a 1-maximal nearly perfect set, and N _p(G) equal the maximum cardinality of a 1-minimal nearly perfect set; introduced by Dunbar et al. in 1995 [206]. See also Kwaśnik and Perl [472].

3.15 Broadcast Numbers

• 1. broadcast time bt(G), minimum time for a vertex in G to complete a broadcast to every other vertex in V , by a series of phone calls, subject to (1) each call involves only two vertices, (2) each call requires one unit of time, (3) a vertex can participate in only one call per unit of time, and (4) a vertex can only call a vertex to which it is adjacent. Broadcasting can also be described in terms of matchings, as follows: Given V ₀ ⊆ V , we seek to broadcast to all vertices from V ₀ by a broadcast sequence V ₀, E ₁, V ₁, E ₂, V ₂, …E _k, V _k = V , where E _i is a matching (not necessarily a perfect matching) between V _i−1 and V _i and V _i = V _i−1 ∪{v : uv ∈ E _i, u ∈ V _i−1}. The broadcast time bt(G) equals the minimum k for which there is a broadcast sequence in G from some vertex V ₀ = {v}; among the first to introduce this were Baker and Shostak in 1972 [30]. There are many different and diverse models of broadcasting in graphs, too numerous to define here, quite a few of which are discussed in the 1988 survey by Hedetniemi et al. [385] and the 1995 survey by Hromkovic et al. [425].

• 2. gossip time gt(G). In broadcasting, one vertex in a graph G has an item of information and needs to communicate it to every other vertex. In gossiping, every vertex in V  has an item of information and needs to communicate it to every other vertex. Thus, broadcasting is a one-to-all process, while gossiping is an all-to-all process. The gossip time is the minimum time for all vertices in a graph to complete a gossip; introduced by Tijdeman in 1971 [611].

• 3. polling time pt(G), minimum time for a vertex in G to poll all of the vertices in a graph, subject to (1) each call involves only two vertices, (2) each call requires one unit of time, (3) a vertex can participate in only one call per unit of time, and (4) a vertex can only call a vertex to which it is adjacent. Polling is the process of completing a broadcast to all vertices and then receiving a response from all vertices. This was introduced by Cheston and Hedetniemi in 1984 [150].

3.16 Pebbling Numbers

Let G = (V, E) be a graph. Let $f: V \rightarrow \mathcal {N}$ be a pebbling function that assigns to each vertex v ∈ V  a nonnegative integer $f(v) \in \mathcal {N}$. We say that v has been assigned f(v) pebbles and that f is a pebbling configuration. Let w(f) =∑_{v ∈ V} f(v) equal the total number of pebbles assigned by the function f. A pebbling move consists of removing two pebbles from a vertex u ∈ V  and then adding one pebble to an adjacent vertex v ∈ N(u). A pebbling configuration f is said to be solvable if for every vertex v ∈ V , there exists a sequence (possibly empty) of pebbling moves that results in a pebble on v.

The concept of pebbling was introduced in 1989 by Chung [155], where she proved that the pebbling number of the n-cube equals 2ⁿ. As with many graph theory parameters, since the introduction of pebbling by Chung, many different variations of pebbling have been studied; the reader is referred to a general discussion of these by Hurlbert [429]. In this subsection we review only a few of the many variants of pebbling.

• 1. pebbling number π(G), minimum number k such that every pebbling configuration $f: V \rightarrow \mathcal {N}$ with w(f) = k is solvable. Thus, the central focus of graph pebbling is to determine a minimum number of pebbles so that no matter how they are placed on the vertices of a graph G, there will always be a sequence of pebbling moves that can move at least one pebble to any specified vertex of G. Consider a path P _n of order n ≥ 1. It is easy to see that if all pebbles are initially placed on one of the two endvertices of P _n, then 2ⁿ⁻¹ pebbles will be required. Thus, pebbling numbers can be exponential in the order n of a graph G.

• 2. optimal pebbling number π ^∗(G). In 1995, Pachtor et al. [520] defined the optimal pebbling number π ^∗(G) to be the minimum weight of a solvable pebbling configuration of G.

• 3. cover pebbling number π _c(G). In cover pebbling the goal is to eventually place pebbles on all vertices of the graph simultaneously. If that can be achieved starting with some particular initial configuration of pebbles, the configuration is called solvable. The cover pebbling number π _c(G) is the minimum integer k such that every configuration containing k pebbles is solvable; cf. Sjöstrand [582] and Crull et al. [175].

• 4. domination cover pebbling number ψ(G). In domination cover pebbling the goal is to eventually place at least one pebble on all the vertices of a dominating set of G. If that can be achieved starting with some particular initial configuration of pebbles, the configuration is called solvable. The domination cover pebbling number ψ(G) is the minimum integer k such that every configuration containing k pebbles is solvable; cf. Gardner et al. [280].

• 5. t-pebbling number π _t(G), minimum weight such that every pebbling configuration weight π _t(G) is t-fold solvable. A pebbling configuration f is said to be t-fold solvable if for every vertex v ∈ V , there exists a sequence (possibly empty) of pebbling moves that results in t pebbles on v; cf. Lourdusamy and Somasundaram [489].

• 6. optimal t-pebbling number $\pi _t^*(G)$, minimum weight of a t-fold solvable pebbling configuration of G: see Herscovici et al. [415].

• 7. t-restricted optimal pebbling number $\pi ^*_t(G)$. A pebbling configuration f is a t-restricted pebbling configuration (abbreviated tRPC) if f(v) ≤ t for all v ∈ V . The t-restricted optimal pebbling number $\pi ^*_t(G)$ is the minimum weight of a solvable tRPC on G; introduced by Chellali et al. [143].

• 8. rubbling number ρ(G). In graph pebbling, only the pebbling move is allowed; while in graph rubbling both pebbling and rubbling moves are available. A rubbling move adds a pebble on a vertex v while removing a pebble from each of two vertices adjacent to v. A rubbling configuration f is said to be solvable if for every vertex v ∈ V , there exists a sequence (possibly empty) of pebbling and rubbling moves that results in a pebble on v. The rubbling number of a graph G, denoted ρ(G), is the minimum number k such that every rubbling configuration of k is solvable.

• 9. optimal rubbling number ρ ^∗(G), minimum weight of a solvable rubbling configuration of G. Rubbling and optimal rubbling were introduced by Belford and Sieben in 2009 [42] and studied by Katona and Papp in [446] and Katona and Sieben in [447].

3.17 Topological Numbers

In integrated circuit design the objective is to place the components of an electrical circuit, such as resistors, capacitors, transistors and inductors, on a plane surface and then connect them with wires in such a way that two wires do not overlap, or cross. This gives rise to the problem of minimizing the number of crossings in a graph drawn on a surface, such as the plane. All of the parameters in this subsection are concerned with embedding graphs on surfaces or decomposing graphs into subgraphs which can be embedded on specific surfaces.

• 1. crossing number ν(G), minimum number of pairwise edge crossings in a plane embedding of G. A plane embedding of a graph G is defined by a function f which assigns to each vertex v ∈ V  a unique point in the plane, and for every edge uv ∈ E, a line is drawn in the plane connecting the two points f(u) and f(v), in such a way that the line connecting u and v does not pass through any points f(w), for any w ∈ V  not equal to u or v. If the line connecting two vertices u and v crosses the line connecting two other vertices w and x, this counts as one pairwise edge crossing. A comprehensive, 113-page survey of many types of crossing numbers has been written by M. Schaefer in 2017 [561]. The interested reader is also referred to the 2016 survey paper by Székely [599].

• 2. bipartite crossing number. A two-layer drawing of a bipartite graph G = (X, Y, E) places vertices in X on one line and those in Y  on another line parallel to the first, and draws edges as straight line segments between the vertices on these two parallel lines. A crossing in a two-layer drawing is a pair of edges that intersect each other at a point not representing a vertex. The bipartite crossing number cr _XY(G) equals the smallest number of crossings possible in a 2-layer drawing of G; cf. Shahrokhi et al. [571], and Kobayashi et al. [458].

• 3. circular crossing number. A circular k-partite drawing of a k-partite graph G is obtained by partitioning a circle into k arc segments, placing the vertices of the i ^th partite set into the ith arc segment, and then drawing the edges as chords of the circle, so that no more than two chords meet at the same crossing. The circular crossing number cpr _k(G) is the minimum number of crossings taken over all circular k-partite drawings, all possible assignments of vertices to arc segments, and all numberings of the parts. This crossing number generalizes both the bipartite crossing number and the outerplanar crossing number; cf. Riskin [541].

• 4. outerplanar crossing number ν ₁(G). An outerplanar or convex drawing of a graph places the vertices on a circle and draws the edges as line segments. The outerplanar crossing number ν ₁(G) is the minimum number of pairs of crossing edges among all such drawings. See Shahrokhi et al. [572], and Czabarka et al. [178].

• 5. rectilinear crossing number. A rectilinear drawing of a graph is one where each edge is drawn as a straight-line segment, and the rectilinear crossing number of a graph is the minimum number of crossings over all rectilinear drawings; cf., for example, Bienstock and Dean [50].

• 6. point-coarseness and point-outercoarseness ξ(G) and ξ ₀, maximum number of subsets into which V(G) can be partitioned so that each subset induces a graph that is homeomorphic from K ₅ or K _3,3, K ₄ or K _2,3, respectively. Two graphs G and H are homeomorphic if they become isomorphic after smoothing all vertices of degree 2, that is removing a vertex v of degree two with neighbors u and w and then adding the edge uw. Point-coarseness was introduced by Mitchem in 1973 [507]. See also Michalak in 1985 [504].

• 7. genus g(G), minimum integer g such that G can be embedded on the orientable surface S _g without any edge crossings/intersections; cf. Walsh et al. [635].

• 8. Hadwiger number had(G), maximum integer k such that the complete graph K _k is a minor of G. A graph H is a minor of a graph G if H can be formed from G by a finite sequence of edge deletions and edge contractions. The famous Hadwiger Conjecture is that for any graph G, χ(G) ≤ had(G). Hadwiger’s Conjecture has been shown to be true for k ≤ 6, and remains open for k > 6; cf. Duchet and Meyniel [205], Robertson and Song [544], Böhme et al. [58], and Chandran and Sivadason [108].

• 9. thickness θ(G), minimum number of planar subgraphs whose union is G; cf. Tutte [614], Beineke [41], Kainen [439], Halton [331], Mutzel et al. [510], and Kawano and Yamazaki [448].

• 10. outerthickness θ ₀(G). A graph is outerplanar if it can be embedded in the plane so that every vertex lies on the outer face, or equivalently, if the graph contains no subdivision of K ₄ or K _2,3. The outerthickness of a graph G is the minimum number of outerplanar graphs whose union is G; cf. Guy and Nowakowski [321] and [322].

• 11. page number pn(G). A book embedding of a graph G consists of an ordering of the vertices V  along the spine of a book and an embedding of each edge uv ∈ E on one page of the book so that no two edges embedded on the same page intersect. The minimum number of pages in a book embedding of G is its page number pn(G); cf. Malitz [496].

4 Conjectures

In this section, we give a sampling of conjectures involving the graph parameters presented in this glossary.

4.1 Basic Structural

We begin with four easy-to-state conjectures.

Conjecture 1 (Erdös and Sós [223])

If G is a graph with average degree at least k − 2 for a positive integer k, then every tree of order k is contained in G as a subgraph.

There are many partial results on this conjecture. For example, McLennon [503] proved that a graph with average degree at least k − 2 contains every tree of order k whose diameter does not exceed 4 as a subgraph.

We now consider the maximum number of edges that must be removed to make a triangle-free graph bipartite.

Conjecture 2 (Erdös et al. [228])

Every triangle-free graph on n vertices can be made bipartite by deleting at most n ²∕25 edges.

This bound, if true, is best possible. Consider a blow-up of a cycle C ₅, that is, replacing each vertex of the C ₅ with k ≥ 1 independent vertices and replacing each edge uv of C ₅ with the complete bipartite graph K _k,k. This conjecture was proved for graphs with at least n ²∕5 edges by Erdös, Gyori and Simonovits in 1991 [232], but the general conjecture remains open.

Given a graph G = (V, E), a vertex-deleted subgraph of G, denoted G _v, is a subgraph formed by deleting exactly one vertex v from G together with all edges containing vertex v. Clearly, G _v is an induced subgraph of G. For a graph G, the deck of G is the multiset of all vertex-deleted subgraphs of G. Each graph in the deck is called a card. Two graphs that have the same deck are said to be hypomorphic. A graphical parameter is recognizable if, for each graph G of order at least 3, it is possible to determine it from the graph’s deck. It is easy to see that all of the basic structural parameters in Section 3.1, e.g. order, size, δ(G), Δ(G), degree sequence, the isolated vertices and leaves are recognizable. This leads to the 1957 conjecture of Kelly [452] and the 1960 conjecture of Ulam [617]:

Conjecture 3 (Reconstruction Conjecture [452, 617])

Any two hypomorphic graphs on at least three vertices are isomorphic.

Note that the requirement that the graphs have at least three vertices is necessary because both graphs on two vertices have the same decks. In 1974, Harary suggested a stronger version of the conjecture [339]:

Conjecture 4 (Set Reconstruction Conjecture [339])

Any two graphs on at least four vertices with the same sets of vertex-deleted subgraphs are isomorphic.

Both the Reconstruction and Set Reconstruction Conjectures have been verified for all graphs with at most 11 vertices by McKay, in 1997 [502]. In a probabilistic sense, it was shown by Bollobás [59] in 1990 that almost all graphs are reconstructible. This means that the probability that a randomly chosen graph on n vertices is not reconstructible goes to 0 as n goes to infinity. In fact, it was shown that not only are almost all graphs reconstructible, but in fact, the entire deck is not necessary to reconstruct them as almost all graphs have the property that there exist three cards in their deck that uniquely determine the graph. Conjecture 3 has been verified for a number of infinite classes of graphs, including regular graphs, trees, disconnected graphs, unit interval graphs, and maximal planar graphs.

4.2 Connectivity and Subgraphs

In 1989 Thomassen [608] conjectured that any graph with high enough connectivity should contain a k-connected spanning, bipartite subgraph.

Conjecture 5 (Thomassen [608])

For all k, there exists a function f(k) such that for all graphs G, if κ(G) ≥ f(k), then G contains a spanning, bipartite H with κ(H) ≥ k.

In 2015 Delcourt and Ferber [191] showed that Conjecture 5 is true up to a log n factor.

In 2003 Kriesell [464] posted the following conjecture related to the connectivity of a graph.

Conjecture 6 (Kriesell [464])

If G is a graph and S a subset of vertices of G such that for any pair u, v ∈ S there are 2k edge-disjoint paths from u to v in G, then G contains k edge-disjoint trees, each of which contains S.

It follows from Mader’s splitting-off theorem (see [493]) that Kriesell’s Conjecture holds if the degree of every vertex in V − S is even. Kriesell’s Conjecture is true if |S|≤ 5.

The concept of toughness was introduced by Chvàtal [156] as a parameter related to the hamiltonicity of a graph. The following conjecture by Chvátal [156] is still open.

Conjecture 7 (The t ₀-Tough Conjecture [156])

There exists a constant t ₀ such that every t ₀-tough graph is Hamiltonian.

For a long time, it was believed that t ₀ = 2 was sufficient for Conjecture 7. However, Bauer et al. [36] showed that if such a constant exists, it must be greater than 2. In fact, they showed that t ₀ ≥ 9∕4 if the conjecture is true.

Conjecture 8 (Thomassen [607])

Every 4-connected line graph is Hamiltonian.

In 1991, Zhan [656] proved that every 7-connected line graph is Hamiltonian. In 1994, Lai [474] proved that every 4-connected line graph of a planar graph is Hamiltonian.

Conjecture 9 (Matthews-Sumner [500])

Every 4-connected claw-free graph is Hamiltonian.

We remark that line graphs are claw-free, so the Matthews-Sumner Conjecture implies the Thomassen conjecture. Fleischner conjectured that the two conjectures were equivalent. This was verified by Ryjáček [549] and the result appeared in 1997.

Conjecture 10 (Sheehan [577])

Every Hamiltonian 4-regular graph has a second Hamiltonian cycle.

Combined with earlier results, Sheehan’s Conjecture would imply that every Hamiltonian r-regular graph (r ≥ 3) has a second Hamiltonian cycle. Thomassen [610] verified this for r ≥ 300.

A graph is called uniquely Hamiltonian if it contains precisely one Hamiltonian cycle. In 2014, Fleischner posed the following conjecture.

Conjecture 11 (Fleischner [266])

Every uniquely Hamiltonian graph has connectivity at most 4.

Fleischner’s Conjecture is true for planar graphs as shown by Tutte in 1956. We remark that Fleischner [266] constructed an infinite family of uniquely Hamiltonian graphs of minimum degree 4 and of arbitrarily high maximum degree. Fleischner [266] also showed that there exist infinitely many uniquely Hamiltonian graphs in which every vertex has degree 4 or 14.

The following conjecture posed by David Barnette originally appeared in [33].

Conjecture 12 (Barnette [33])

Every 3-connected cubic planar bipartite graph is Hamiltonian.

Holton et al. [419] proved Barnette’s conjecture for up to 64 vertices, inclusive. Subsequently, the conjecture has been shown to be true for up to 84 vertices, inclusive.

Thomassen [609] posed the following conjecture about chords of longest cycles. A chord of a cycle C is an edge e so that e∉E(C), but both ends of e are in V (C).

Conjecture 13 (Thomassen [609])

If G is a 3-connected graph, every longest cycle in G has a chord.

A graph G is said to be locally connected if the subgraph induced by the open neighborhood of each vertex of G is connected, and G is locally k-connected if G[N(v)] is k-connected for every v ∈ V (G). Chartrand and Pippert [114] proved that every connected, locally connected graph of order at least 3 with maximum degree at most 4 is either Hamiltonian or the complete tripartite graph K _1,1,3. In 1979, Oberly and Sumner [517] proved the following theorem and made a stronger conjecture.

Theorem 2 ([517])

If G is a connected, locally connected, K _1,3 -free graph of order at least 3, then G is Hamiltonian.

Conjecture 14 (Oberly-Sumner [517])

If G is a connected, locally k-connected, K _1,k+2-free graph of order at least 3, then G is Hamiltonian.

Note that Theorem 2 shows that Conjecture 14 is true for k = 1.

A factor of a graph G is a spanning subgraph of G. A graph G is factorable into factors F ₁, F ₂, …F _t if these factors are (pairwise) edge-disjoint and $\bigcup _{i=1}^t E(F_i) = E(G)$. If G is factorable into factors F ₁, F ₂, …F _t, then {F ₁, F ₂, …, F _t} is called a factorization of G. Further, if F _i = H for 1 ≤ i ≤ t in a factorization of G, then G is said to be H-factorable and G has an isomorphic factorization into copies of H. An k-regular factor of G is called an k-factor, and if G has a factorization into k-factors, then G is k-factorable. In particular, a 1-factor of G is a perfect matching of G.

It is believed that the following conjecture originated in a paper by Chetwynd and Hilton [151].

Conjecture 15 (The 1-Factorization Conjecture)

If G is an r-regular graph of even order n such that (1) r ≥ n∕2 if n ≡ 2(mod 4) or (2) r ≥ (n − 1)∕2 if n ≡ 0(mod 4), then G is 1-factorable.

Nash-Williams [513] conjectured that r-regular graphs can be factored into Hamiltonian cycles and possibly one 1-factor.

Conjecture 16 (Nash-Williams [513])

If G is an r-regular graph of even order n such that r ≥ n∕2, then G can be factored into Hamiltonian cycles and at most one 1-factor.

Csaba et al. [176] showed that both Conjectures 15 and 16 hold for sufficiently large n.

The following conjecture was made independently by Szekeres [600] in 1973 and Seymour [566] in 1979. This conjecture, known as the Cycle Double Cover Conjecture, is now widely considered to be among the most important open problems in graph theory.

Conjecture 17 (Cycle Double Cover Conjecture)

For every graph G with no bridge, there is a list of cycles in G so that every edge appears in exactly two cycles.

We remark that the list may have repeated cycles, as is the case with C _n. Fan [242] used Seymour’s 6-flow theorem [567] to prove that G has a list of cycles so that every edge is contained in exactly six cycles. The Cycle Double Cover Conjecture is known to be true for every 4-edge-connected graph.

A k-cycle is a cycle of length k. Next we give a well-known conjecture of Erdös and Gyárfás [225].

Conjecture 18 (Erdös - Gyárfás [225])

For every graph G with minimum degree at least 3, there exists a non-negative integer k such that G contains a cycle of length 2^k.

Conjecture 18 is among the many problems for whose solution Erdös offered money. Heckman and Krakovski [377] proved the conjecture is true for 3-connected cubic planar graphs. They actually proved a stronger result by showing that every 3-connected, cubic, planar graph contains a cycle of length 2^k for some 2 ≤ k ≤ 7. The conjecture also holds for planar claw-free graphs [180] and for K _1,k-free graphs having minimum degree at least k + 1, or maximum degree at least 2k − 1 [576]. Other partial results have been obtained, but the general conjecture is still open.

It is well-known that every two longest paths in a connected graph have a common vertex. Skupien [583] gave examples of connected graphs where seven longest paths do not share a common vertex.

Conjecture 19 (Gallai [276])

If G is a connected graph, then every three longest paths have a vertex in common.

4.3 Distance and Degree

A graph G is called diameter-2-critical if its diameter is two, and the deletion of any edge increases the diameter. The following conjecture was made independently by Murty and Simon (see [93]).

Conjecture 20 (Murty-Simon Conjecture)

If G is a diameter-2-critical graph with n vertices and m edges, then m ≤⌊n ²∕4⌋, with equality if and only if G is the complete bipartite graph $K_{\left \lfloor \frac {n}{2} \right \rfloor , \left \lceil \frac {n}{2} \right \rceil }$.

According to Füredi [274], Erdös said that this conjecture goes back to the work of Ore in the 1960s. Fan [241] proved the conjecture for n ≤ 24 and for n = 26. In 1992 Füredi [274] gave an asymptotic result proving the conjecture is true for large n, that is, for n > n ₀ where n ₀ is a tower of 2’s of height about 10¹⁴. The conjecture remains open for general n.

Our next three conjectures involve the indices having applications in chemistry, including the problem of finding a compound with a given Wiener index. A major conjecture in this area is whether every positive integer is the Wiener index of some tree.

Conjecture 21 (Wiener Index Conjecture [147, 305, 480])

For every positive integer k (except for some finite set), there exists a tree T with σ(T) = k.

Conjecture 22 (DeLaViña and Waller [189])

If G is a graph of diameter d ≥ 3 and order 2d + 1, then σ(G) ≤ σ(C _2d+1).

The next conjecture relates the Randić connectivity index R(G) to the average distance μ(G).

Conjecture 23 (Fajtlowicz [239])

For all connected graphs G, R(G) ≥ μ(G).

Li and Shi [485] proved Conjecture 23 for graphs G having order n ≥ 15 and minimum degree δ(G) ≥ n∕5, and Cygan et al. [177] proved it for trees.

4.4 Labeling

A graph with m edges is graceful if the vertices can be assigned distinct numbers from among 0, 1, …, m, so that the differences along the edges are precisely 1, 2, …, m. A dynamic survey, of some 415 pages, on graph labelings has been written by Gallian [278]. The following conjecture, posed by Kotzig, Ringel and Rosa, has attracted much attention.

Conjecture 24 (Graceful Tree Conjecture)

Every tree is graceful.

A graph of order n is called prime if one can bijectively label its vertices with integers 1, …, n so that whenever two vertices are adjacent, their labels are relatively prime. According to Gallian [278], this concept was introduced by Entringer, who made the following conjecture.

Conjecture 25

Every tree is prime.

Haxell et al. [356] proved Conjecture 25 for trees having large enough order. The conjecture is also proven for several families of graphs in [613].

The next conjecture involves the L(2, 1)-labeling number λ(G).

Conjecture 26 (Griggs and Yeh [313])

For any graph G with maximum degree Δ(G) = Δ, λ(G) ≤ Δ ².

Conjecture 26 is known as the Δ ²-conjecture and considered the most important open problem in L(2, 1)-labeling. In their introductory paper, Griggs and Yeh [313] proved that λ(G) ≤ Δ ² + 2Δ, and the best bound to date is Δ ² + Δ − 2 shown by Goncalves [308]. Havet et al. [354] showed that Conjecture 26 holds for sufficiently large Δ. Most of the work on this conjecture deals with particular classes of graphs.

4.5 Decomposition

As we have seen, a path-decomposition of a graph G is a set of paths whose edges partition the edge set of G. Equivalently, a path-decomposition is a vertex partition π = {V ₁, V ₂, …, V _k} such that for 1 ≤ i ≤ k, the subgraph G[V _i] induced by V _i is a path, and every edge uv ∈ E is contained exactly one such path. Our next conjecture is due to Gallai (see [490]).

Conjecture 27 (Gallai)

If G is a connected graph on n vertices, then G can be decomposed into $\left \lceil n/2 \right \rceil$ paths.

In 1968 Lovász [490] showed that a relaxed form of Conjecture 27 holds when he proved that every graph on n vertices has a decomposition consisting of $\left \lceil n/2 \right \rceil$ paths and cycles. Conjecture 27 has also been verified for many families of graphs, for example, see [68, 185, 243, 251, 348, 529].

4.6 Covering and Matching

Recall that ν ₃(G) is the maximum number of pairwise edge-disjoint triangles in G. In 1981, Tuza [615, 616] conjectured the following upper bound on the triangle cover number τ ₃(G).

Conjecture 28 (Tuza [615, 616])

For any graph G, τ ₃(G) ≤ 2ν ₃(G).

Conjecture 28 has been well-studied and many partial results obtained. For example, Puleo [526] proved the conjecture for all graphs having no subgraph with average degree at least 7. Fractional relaxations on the bound have been obtained. Haxell [355] provided the best such result by showing that τ(G) ≤ 2.87ν(G) for all graphs G.

The next well-known conjecture is attributed to Berge in [565], but it first appeared in [273].

Conjecture 29 ([273, 565])

Every cubic bridgeless graph G contains six perfect matchings such that each edge of G is contained in precisely two of the matchings.

4.7 Coloring

We now consider several conjectures involving graph coloring. It is well-known that the clique number ω(G) is a sharp lower bound on the chromatic number χ(G) for any graph G. Reed [540] conjectured in 1998 an upper bound on χ(G) also involving ω(G). Recall that Δ(G) denotes the maximum degree of G.

Conjecture 30 (Reed [540])

For every graph G,

$$\displaystyle \begin{aligned}\chi(G) \le \left\lceil{\frac{\omega(G) + 1 + \varDelta(G)}{2}}\right \rceil.\end{aligned}$$

If G has χ(G) = k, then G is said to be a k-chromatic graph. A graph H is a subdivision of a graph G is H can be obtained from G by inserting vertices of degree two into some, all, or none of the edges of G. Hajós [326] conjectured that a k-chromatic graph contains a subdivision of the complete graph K _k as a subgraph.

Conjecture 31 (Hajós [326])

If G is a k-chromatic graph for k ≥ 2, then G contains a subdivision of K _k.

Catlin [104] gave counterexamples to Conjecture 31 showing that the conjecture is false for k ≥ 7. Hence, Conjecture 31 is open only for small values of k.

Erdös, Faber, and Lovász (see [224]) formulated the following graph coloring conjecture in 1972.

Conjecture 32 (Erdös-Faber-Lovász Conjecture)

Every graph which can be decomposed into k complete graphs on k vertices (such that every pair of complete graphs has at most one shared vertex) is k-colorable.

We remark that the Erdös-Faber-Lovász Conjecture can be restated in the language of hypergraphs as follows: In every k-uniform linear hypergraph H with k hyperedges, one may color the vertices of H with k colors in such a way that each hyperedge has one vertex of each color.

Given two graphs G and H, we say H is a minor of G if H can be obtained from G by a series of operations: contracting edges, deleting isolated vertices and deleting edges. The following conjecture, due to Hadwiger [324] in 1943, is a generalization of the four color theorem and is perhaps the most challenging conjecture in graph theory.

Conjecture 33 (Hadwiger’s Conjecture [324])

Every k-chromatic graph G contains the complete graph K _k as a minor.

Bollobàs et al. [64] claimed that Conjecture 33 is “one of the deepest unsolved problems in graph theory” and showed it holds for almost every graph. Hadwiger [324] proved the conjecture for k ≤ 4 in 1943 when he introduced his conjecture. Before Hadwiger’s Conjecture was formally posed, Wagner [632] had already shown that the case k = 5 is equivalent to the Four Color Theorem. Hence, Hadwiger’s Conjecture 33 is true for k = 5. Also using the Four Color Theorem, Robertson et al. [545] settled the conjecture for k = 6; their paper with this proof won the 1994 Fulkerson Prize. Hence, Conjecture 33 is true for 1 ≤ k ≤ 6, but it remains unsolved for all k > 6.

The categorical product G × H of two graphs G and H is the graph with vertex set V (G) × V (H) and edges (u, v)(u′, v′) ∈ E(G × H) if and only if uv ∈ E(G) and vv′∈ E(H). In 1966, Hedetniemi [378] made the following conjecture on the chromatic number of categorical products.

Conjecture 34 (Hedetniemi’s Conjecture [378])

For any graphs G and H, χ(G × H) = min{χ(G), χ(H)}.

The interested reader is referred to Hedetniemi’s chapter [380] in Volume 1 of this series [287] and to the following three survey papers on Hedetniemi’s Conjecture by Zhu [661], Sauer [560] and Tardif [601].

A similar conjecture was made for the circular chromatic number in [660].

Conjecture 35 (Zhu [660])

For any graphs G and H, χ _c(G × H) = min{χ _c(G), χ _c(H)}.

In a 2001 survey paper on circular chromatic numbers, Zhu [662] remarks that Conjecture 35 is equivalent to the following conjecture.

Conjecture 36 (Zhu [662])

For any number r, if G and H are not r-circular colorable, then G × H is also not r-circular colorable.

When r is an arbitrary integer, this becomes Hedetniemi’s Conjecture (Conjecture 34). Conjecture 36 is known to be true for r = 1, r = 2, and r = 2 + 1∕k, where k is any positive integer (see [221, 325, 662]). As far as we know, the problem is open for all other values of r.

Vizing’s Theorem [626] is a major result for edge coloring.

Theorem 3 (Vizing’s Theorem [626])

For any non-empty graph G,

$$\displaystyle \begin{aligned}\varDelta(G) \le \chi'(G) \le \varDelta(G) + 1.\end{aligned}$$

A graph is said to belong to Class 1 if χ′(G) = Δ(G) and to Class 2 if χ′(G) = Δ(G) + 1.

For each k where k = Δ(G) ≤ 5, there exists planar graph having Δ(G) = k of Class 1 and a planar graph of Class 2. Vizing [626] showed that every planar graph G with Δ(G) ≥ 8 is of Class 1, and conjectured that every graph with Δ(G) ∈{7, 8} is of Class 1. In 2001, Sanders and Zhao [559] verified the case for Δ(G) = 7. Hence, Vizing’s conjecture is as follows.

Conjecture 37 (Vizing [626])

If G is a planar graph with Δ(G) = 6, then G is of Class 1.

A subgraph H with order n′ and size m′ is called an overfull subgraph of G if n′ is odd and m′ > Δ(G) ⋅ (n − 1)∕2. Chetwynd and Hilton [151] conjectured that for graphs G with order n and Δ(G) > n∕3, G belongs to Class 2 if and only if G contains an overfull subgraph.

Conjecture 38 (Chetwynd and Hilton [151])

Let G be a graph with order n and Δ(G) > n∕3. Then G belongs to Class 2 if and only if G contains an overfull subgraph.

Behzad [40] and Vizing [625] independently conjectured that a bound similar to the upper bound of Vizing’s Theorem on the edge chromatic number holds for the total chromatic number.

Conjecture 39 ([40, 625])

For every graph G, χ ^′′(G) ≤ Δ(G) + 2.

The following conjecture involving the edge chromatic number χ′(G) and the list chromatic index $\chi ^{\prime }_l(G)$ first appeared in [62].

Conjecture 40 ([62])

For every nonempty graph G, $\chi '(G) = \chi ^{\prime }_l(G)$.

The next conjecture involves the strong chromatic index $\chi ^{\prime }_s(G)$.

Conjecture 41 (Burris and Schelp [92])

If G is a graph of order n and every component of G has order 3 or more, then $\chi ^{\prime }_s(G) \le n+1$.

We next consider nonproper edge colorings. Given an edge coloring of a graph, the induced color of a vertex is the sum of the colors of its incident edges. The following conjecture, explored by Chartrand [113] in Volume 1 of this series [287], is due to Karoński et al. [444].

Conjecture 42 (The 1-2-3 Conjecture [444])

For every connected graph G of order 3 or more, each edge of G can be assigned one of the colors 1, 2, 3 in such a way that the induced colors of every two adjacent vertices are different.

Karoński et al. [444] showed that there is an infinite class of graphs for which the 1-2-3 Conjecture holds. They also proved that the conjecture holds for connected graphs of order 3 or more having chromatic number at most 3. We note that if you allow four colors, then the conjecture is true.

Our final conjecture in this subsection involves the achromatic number ψ(T) and the pseudo-achromatic number ψ _s(T) of trees T. For more details on this conjecture, the reader is referred to [380] in Volume 1 of this series [287], and to Edwards [218].

Conjecture 43 (Achromatic-Pseudoachromatic Tree Conjecture)

For any tree T, ψ(T) ≤ ψ _s(T) ≤ ψ(T) + 1.

4.8 Domination

We next give sampling of conjectures involving domination. Arguably the main open problem in the area of domination in graphs is Vizing’s Conjecture, posed as a problem in [624] and later as a conjecture in [627]. Vizing’s conjecture asserts that the domination number of the Cartesian product of two graphs is at least as large as the Cartesian product of their domination numbers.

Conjecture 44 (Vizing’s Conjecture 1963 [624, 627])

For graphs G and H,

In 2000, Clark and Suen [157] proved the looser result that for all graphs G and H, $\gamma (G\square H)\geq \frac {1}{2}\gamma (G)\gamma (H)$. Suen and Tarr [597] strengthened Clark and Suen’s result by showng that $\gamma (G\square H)\geq \frac {1}{2}\gamma (G)\gamma (H)+\frac {1}{2}\min \{\gamma (G),\gamma (H)\}$. Furthermore, Krop [466, 467] proved that for any graphs G and H, $\gamma (G\square H)\geq \frac {\gamma (G)}{2\gamma (G)-1}\gamma (G)\gamma (H)$, and if G is claw-free or P ₄-free, then $\gamma (G\square H)\geq \frac {2}{3}\gamma (G)\gamma (H)$. Employing the packing number, Brešar [74] also improved the result of Clark and Suen. However, Vizing’s Conjecture still remains open. For a survey on Vizing’s Conjecture in 2012, see [78].

Reed [539] conjectured that the domination number of a connected, cubic graph of order n is at most $\left \lceil n/3 \right \rceil$. But Kostochka and Stodolsky [462] gave a counterexample to disprove this conjecture. However, Kostochka and Stodolsky [462] and Kelmans [453] independently claim that Reed’s conjecture holds for 3-connected cubic graphs.

Conjecture 45 (Kostochka and Stodolsky [462], Kelmans [453])

If G is a 3-connected cubic graph of order n, then $\gamma (G) \le \left \lceil \frac {n}{3} \right \rceil$.

In Chapter 15 of the first volume of this series, Henning [407] discusses other families for which Reed’s bound is conjectured to hold and poses the following.

Conjecture 46 (Henning [407])

If G is a cubic, bipartite graph of order n, then $\gamma (G) \le \frac {n}{3}$.

The next two conjectures claim that given large enough girth, Reed’s bound holds.

Conjecture 47 (Verstraete’s Domination Conjecture [407])

If G is a connected, cubic graph on n vertices with girth at least 6, then $\gamma (G) \le \frac {1}{3}n$.

Recall that i(G) is the independent domination number of G.

Conjecture 48 (Verstraete’s Independent Domination Conjecture [621])

If G is a connected, cubic graph on n vertices with girth at least 6, then $i(G) \le \frac {1}{3}n$.

Note that for every graph G, γ(G) ≤ i(G). Thus, Conjecture 48 is a stronger conjecture that Conjecture 47.

We next consider a conjecture involving the ratio of the independent domination and the domination numbers.

Conjecture 49 (Rad and Volkmann [530])

If G is a graph with maximum degree Δ(G) ≥ 6, then i(G)∕γ(G) ≤ Δ(G)∕2.

Wang and Wei [637] proved Conjecture 49 for trees.

Recall that the k-domination number γ _k(G) denotes the minimum cardinality of a dominating set S having the property that for every vertex v ∈ V − S, |N(v) ∩ S|≥ k.

Conjecture 50 (Fink and Jacobson [263])

For a graph G with δ(G) ≥ k, there exists function f(k) such that for j ≥ f(k), γ _k(G) < γ _j(G).

Our next conjectures involve the total domination number γ _t(G). Thomasse and Yeo [606] posed the following $\frac {4}{11}$-conjecture.

Conjecture 51 (Thomasse, Yeo [606])

If G is a graph of order n with δ(G) ≥ 5, then $\gamma _t(G) \le \frac {4}{11}n$.

Henning and Yeo believe the 4∕11-bound can be improved to a 1∕3-bound if we forbid 4-cycles. Recall that a graph is quadrilateral-free if it contains no 4-cycles, not necessarily induced.

Conjecture 52 (Henning, Yeo [413])

If G is a quadrilateral-free graph of order n with δ(G) ≥ 5, then $\gamma _t(G) \le \frac {1}{3}n$.

Conjecture 53 (Henning [405])

If G is a planar graph of diameter 3, then γ _t(G) ≤ 6.

A graph G is called total domination edge critical if γ _t(G + e) < γ _t(G) for every edge $e \in E(\overline {G})$. Further, if γ _t(G) = k, then we say that G is a k _t -critical graph. This concept was introduced in [619] and, in the same paper, the authors showed that the addition of an edge to a graph can change the total domination number by at most 2. Total domination edge critical graphs G with the property that γ _t(G) = k and γ _t(G + e) = k − 2 for every edge $e \in E(\overline {G})$ are called k _t -supercritical graphs.

Hanson and Wang [334] showed that a graph is diameter 2-critical if and only if its complement is 3_t-critical or 4_t-supercritical, relating this concept to the Murty-Simon Conjecture (Conjecture 20). The 4_t-supercritical graphs were characterized in [618] as the disjoint unions of two complete graphs. Since the complement of a 4_t-supercritical graph is a complete bipartite graph and the number of edges is minimized when the partite sets are of equal cardinality, Conjecture 20 holds for this case. Therefore, proving Conjecture 20 is equivalent to proving the following conjecture.

Conjecture 54

If G is a 3_t-critical graph with order n and size m, then $m(G) > \frac {n(n-2)}{4}$.

In [619] it was proved that any 3_t-critical graph has diameter 2 or 3. After the result of Hanson and Wang in [334], Conjecture 54 was verified in [334, 371] for the 3_t-critical graphs of diameter 3. Conjecture 54 remains open for the 3_t-critical graphs of diameter 2.

Balbuena et al. [32] posed the following stronger conjecture.

Conjecture 55 (Balbuena, et al. [32])

If G is a 3_t-critical graph with order n, size m, and diam(G) = 2, then m ≥⌊(n ² − 4)∕4⌋.

The following conjecture on paired domination was posed by Henning in [407].

Conjecture 56 (Henning [407])

If G is a bipartite, cubic graph of order n, then $\gamma _{\mathrm {pr}}(G) \le \frac {1}{2}n$.

Recall that γ ⁻¹(G) and α(G) denote the inverse domination number and the vertex independence number, respectively. The following conjecture first appeared in [471] as a “theorem,” but later an error was found in the proof.

Conjecture 57

For any isolate-free graph G, γ ⁻¹(G) ≤ α(G).

Although to date Conjecture 57 remains unsettled, several partial results offer support of its validity. For more information on Conjecture 57 and these results, the reader is referred to Hedetniemi’s chapter [380] in Volume 1 of this series [287].

Our next conjecture is an upper bound on the Roman domination number in terms of the order of a graph. It is known that $\gamma _R(G) \le n - {\frac {\gamma (G)}{2}}$ where n ≥ 3 and the domination number γ(G) ≥ 2 (see Favaron et al. [255]). Also, Chambers et al. [106] proved that $\gamma _R(G) \le {\frac {8n}{11}}$ for any graph G with order n ≥ 9 and minimum degree at least 2.

Bermudo et al. [46] proved that the Roman domination number and the differential are complementary with respect to the order n of the graph G, that is, ∂(G) + γ _R(G) = n. Hence, determining a bound on one of them with respect to n yields a bound on the other. Using this fact, Bermudo [45] proved that for any graph G with order n ≥ 9 and minimum degree at least 2, $\partial (G) \ge {\frac {3\gamma (G)}{4}}$, and so, $\gamma _R(G) \le n - {\frac {3\gamma (G)}{4}}$. Furthermore, Bermudo [45] conjectures that these bounds can be improved for graphs with minimum degree at least 3.

Conjecture 58 (Bermudo [45])

If G is a graph with minimum degree at least 3, then ∂(G) ≥ γ(G).

Conjecture 58 can be stated equivalently in terms of Roman domination as follows.

Conjecture 59 (Bermudo [45])

If G is a graph with minimum degree at least 3, then γ _R(G) ≤ n − γ(G).

The next two conjectures involve the bondage number b(G) of a graph G.

Conjecture 60 (Teschner [604])

For any graph G, $b(G) \le {\frac {3}{2}} \varDelta (G)$.

Teschner [604] proved that Conjecture 60 holds for graphs having domination number at most 3. Hartnell and Rall [350] and Teschner [605] showed that the bound of Conjecture 60 is sharp for the Cartesian product . Dunbar et al. [211] conjecture the following upper bound on the bondage number.

Conjecture 61 (Dunbar et al. [211])

If G is a planar graph with maximum degree Δ(G), then b(G) ≤ Δ(G) + 1.

Kang and Yuan [441] have shown that for any connected planar graph G, b(G) ≤ min{8, Δ(G) + 2}, solving Conjecture 61 for planar graphs with Δ(G) ≥ 7 and Conjecture 60 for planar graphs with Δ(G) ≥ 4.

Next we consider a conjecture involving the paired domination subdivision number.

Conjecture 62 (Favaron et al. [256])

For every connected graph G of order n ≥ 3, $sd_{\gamma _{pr}}(G) \le n-1$.

A graph G is called irredundance perfect if ir(H) = γ(H), for every induced subgraph H of G. A graph that is not irredundance perfect is called irredundance imperfect. We conclude this subsection with two conjectures involving irredundance perfect graphs.

Conjecture 63 (Volkmann and Zverovich [630])

The number of minimal irredundance imperfect graphs is finite.

In [630], Volkmann and Zverovich modified a conjecture of Henning [402] as follows.

Conjecture 64

A graph G is irredundance perfect if and only if G is 5-irredundance perfect.

4.9 Domatic

Recall that the domatic number d(G) of a graph G is the maximum number of disjoint dominating sets in G. The following conjecture was first posed as a question by Kostochka in 2009: Is it true that the vertex set of every cubic, bipartite graph can be partitioned into three dominating sets? This question was subsequently posed as a conjecture by Henning [407] in Volume 1 of this series [287].

Conjecture 65 (Henning [407])

If G is a cubic, bipartite graph, then d(G) = 3.

Recall that the total domatic number d _t(G) of a graph G is the maximum number of disjoint total dominating sets. We remark that this parameter is equivalent to the minimum (not necessarily proper) coloring of the vertices of a graph where every color appears in every open neighborhood. Such a coloring in called the coupon coloring problem by Chen et al. [149].

Goddard and Henning [295] showed that if G is a planar graph, then d _t(G) ≤ 4 and this bound is best possible. Further, they showed that if G is a toroidal graph, then d _t(G) ≤ 5 and this bound is best possible. By a planar triangulation we mean a maximal planar graph. Goddard and Henning [295] posed the following conjecture about the total domatic number of planar triangulations.

Conjecture 66 (Goddard, Henning [295])

If G is a planar triangulation of order at least 4, then d _t(G) ≥ 2.

Conjecture 67 (Goddard, Henning [295])

Every planar triangulation with at least four vertices has a proper 4-coloring (C ₁, C ₂, C ₃, C ₄) such that C ₁ ∪ C ₂ and C ₃ ∪ C ₄ are total dominating sets.

Equivalently, Conjecture 67 claims that V (G) can be partitioned into two total dominating sets both of which induce a bipartite subgraph of G. The authors in [295] show that if G is a planar triangulation and the dual of G is Hamiltonian, then Conjecture 66 holds. As remarked in [295], to prove Conjecture 66 it would be enough to show that every 3-connected cubic planar graph has a 2-factor that does not include a facial cycle. If one imposes larger minimum degree, it appears that even more can be said.

Conjecture 68 (Goddard, Henning [295])

If G is a planar triangulation with δ(G) ≥ 4, then d _t(G) ≥ 3.

It is noted in [295] that if Conjecture 68 is true, then the bound is sharp, and the authors in [295] also posed the following conjecture.

Conjecture 69 (Goddard, Henning [295])

If G is a connected cubic graph, then G has a family of four (not necessarily distinct) total dominating sets such that every vertex is in at most two of these.

4.10 Pebbling

Chung [155] attributed the following conjecture to Graham.

Conjecture 70 (Graham’s Conjecture [155])

For graphs G and H,

We conclude this subsection with an open question on optimal pebbling.

Question ([89])

Is it true that $\pi ^{\ast }(G)\leq \left \lceil n/2\right \rceil$ whenever G is a connected n-vertex graph with minimum degree at least 3?

4.11 Topological

Determining the crossing number of the complete bipartite graph, known as Turan’s brick factory problem, is one of the oldest and most famous crossing number problems. Zarankiewicz [649] conjectured an exact value.

Conjecture 71 (Zarankiewicz [649])

For the complete bipartite graph K _m,n,

$$\displaystyle \begin{aligned}\nu(K_{m,n}) = \left \lfloor{\frac {n}{2}}\right\rfloor \left\lfloor {\frac {n-1}{2}}\right\rfloor \left\lfloor {\frac {m}{2}}\right\rfloor \left\lfloor {\frac {m-1}{2}}\right\rfloor.\end{aligned}$$

Kleitman [455] proved that Conjecture 71 holds for complete bipartite graphs K _m,n for min(m, n) ≤ 6.

Guy [320] posed a similar conjecture for complete graphs.

Conjecture 72 (Guy [320])

For the complete graph K _n,

$$\displaystyle \begin{aligned}\nu(K_{n})={\frac {1}{4}}\left\lfloor {\frac {n}{2}}\right\rfloor \left\lfloor {\frac {n-1}{2}}\right\rfloor \left\lfloor {\frac {n-2}{2}}\right\rfloor \left\lfloor {\frac {n-3}{2}}\right\rfloor.\end{aligned}$$

5 New Parameters and Open Problems

It seems only natural that any careful study of graph theory parameters will lead to the discovery of new parameters or parameters which have been defined but little studied. In the course of writing this glossary, quite a number of these parameters have come to mind, which might be worth studying. In this section we present these for your consideration. We cannot vouch 100% for the originality of some of these parameters; it has been joked that “no one ever discovers anything for the first time.” We can only say that as of the publication of this chapter, we are not aware that some of these parameters have been defined or under what name, or if they have been studied. Of course, we are always reminded that just because it hasn’t been defined, it doesn’t mean that it is worth studying; only time will tell.

5.1 β-Packing Number

A β-packing of a graph G is a maximal set S having the property that for all vertices v ∈ V − S, |N(v) ∩ S|∕deg(v) ≤ β.

This is inspired by α-domination, as originally defined and studied by Dunbar et al. [214]. A set S is called an α-dominating set, for some value α, 0 < α ≤ 1, if for every vertex v ∈ V − S, |N(v) ∩ S|∕deg(v) ≥ α. The α-domination number of a graph G equals the minimum cardinality of an α-dominating set in G, and is denoted γ _α(G). Similarly, the β-packing number equals the maximum cardinality of a β-packing set in G, which could be denoted by ρ _β(G).

5.2 Upper Binding Number

In Section 3.2 we define the binding number, bind(G) = min{|N(X)|∕|X| : X ⊆ V, N(X) ≠ V }. For this parameter, we could just as well ask, what about the maximum? Let the upper binding number be Bind(G) = max{|N(X)|∕|X| : X ⊆ V, N(X) ≠ V }. It follows that bind(G) ≤ δ(G) ≤ Δ(G) ≤ Bind(G). Furthermore, if N(X) = V , then X is a total dominating set, and therefore, bind(G) ≤ n∕γ _t(G) ≤ Bind(G).

5.3 Broadcasting in Trees with Multiple Originators

There are several papers that consider the problem of partitioning or decomposing trees into sub-trees of various types:

In [246], Farley, Hedetniemi and Proskurowski give a linear algorithm for partitioning the vertices of a tree into a minimum number of sub-trees of diameter at most k. In [640], Yan, Chang, Hedetniemi and Hedetniemi give a linear algorithm for decomposing a tree into a minimum number of paths each of which has at most k vertices. So consider variations on this theme. Partition the vertices (or edges) of a tree into a minimum number of sub-trees, each of a given type. What types would you choose?

Let us suggest minimum broadcast trees. In fact, let us suggest an even more general problem at the same time. Let S ⊆ V  be an arbitrary subset of vertices, which act as originators of some common message. Each vertex in S makes a phone call to one neighbor and relays the information, at time t = 1. At time t ≥ 2, any vertex having this information can make a phone call to one neighbor not having this information. This is repeated every time step until all vertices in the graph have received the information.

Thus, we have two parameters: the number of originators, and the amount of time to complete the broadcast. We can define the following parameters:

Let b _t(G) equal the minimum number of originators necessary to complete broadcasting within time t in a graph G. Note that any b _t-set is, by definition, a distance t dominating set. But a minimum distance t dominating set in general can be much smaller than b _t(G).

Let b _k(G) equal the minimum number of time steps necessary to reach all vertices of G from a set of k originators.

In particular, consider these two problems when restricted to trees.

In [591], Slater, Cockayne and Hedetniemi develop an algorithm to find all single vertices from which a broadcast can be completed in minimum time in an arbitrary tree. They show that this broadcast center always consists of a star with two or more vertices. Thus, in this paper they give an algorithm for computing the value b ₁(T).

Can you construct polynomial algorithms for computing the values of b _k(T) for any tree T?

5.4 Cycle Number Cycle(G)

The definition of the cycle number cycle(v) in Section 3.2, as the number of distinct cycles containing vertex v, suggests that one define the cycle number Cycle(G) = max{cycle(v) : v ∈ V }. Similarly, the cycle center CC(G) of a graph G consists of the set of vertices v for which cycle(v) is a maximum. What can you say about the cycle center of a graph G?

5.5 Concave Number ccv(G) and Weakly Convex Number wcvx(G)

The definition of a convex set in Section 3.3 suggests the following two parameters. A set S is said to be concave if for every pair of vertices u, v ∈ S, no shortest u − v path contains a vertex other than u and v in S. The concave number or the concavity ccv(G) is the maximum cardinality of a concave set in G. Note, for example, that any clique in a graph G is a concave set. Similarly, the set of all leaves in a tree is a concave set. Indeed, we conjecture that for any nontrivial tree T, ccv(T) equals the number of leaves of T.

A set S is said to be weakly convex if for every pair of vertices u, v ∈ S there exists a u − v geodesic, every vertex of which belongs to S. Since, by definition, the entire vertex set V  is weakly convex, and convex, we seek either the maximum order of a proper subset of vertices that is weakly convex, or the minimum order of a maximal weakly convex set in a graph G.

5.6 Degree-Defined Sets

Let S ⊆ V  be an arbitrary set of vertices and consider the three induced subgraphs G[S], G[V − S] and the bipartite subgraph G[S, V − S] induced by the set of edges between vertices in S and vertices in V − S. Let deg _u G[S] denote the degree of a vertex u ∈ S in G[S]; deg _v G[V − S] the degree of a vertex v ∈ V − S in G[V − S]; deg _u G[S, V − S] the degree of a vertex u ∈ S in G[S, V − S] and deg _v G[V − S, S] the degree of a vertex v ∈ V − S in G[V − S, S].

By placing conditions on the various combinations of these degrees one defines a wide variety of sets, many of which have been studied. However, even more have received little or no attention, including those in bold in the table below. The basic framework of the table below is due to Telle [602] in his PhD thesis; parts of this table appear on page 292 of [361]. In the table, X denotes that the degree of the vertex can be anything, i.e. it does not matter. We also assume that the graph G in question is a non-trivial connected graph.

Type of set	deg u G[S]	deg u G[S, V − S]	deg v G[V − S, S]	deg v G[V − S]
1. dominating	X	X	≥1	X
2. total/open dominating	≥1	X	≥1	X
3. maximal induced matching	1	X	≥1	X
4. 1-dependent dominating	0,1	X	≥1	X
5. independent dominating	0	X	≥1	X
6. perfect dominating	X	X	1	X
7. perfect total dominating	≥1	X	1	X
8. perfect induced matching	1	X	1	X
9. 1-dependent perfect dominating	0,1	X	1	X
10. efficient dominating	0	X	1	X
11. nearly perfect	X	X	0, 1	X
12. total nearly perfect	≥1	X	0, 1	X
13. nearly perfect induced matching	1	X	0, 1	X
14. open packing/total nearly perfect	0,1	X	0, 1	X
15. packing	0	X	0, 1	X
16. restrained dominating	X	X	≥1	≥1
17. dominating bipartition	X	≥1	≥1	X
18. Nearly perfect bipartition	X	0, 1	0, 1	X
19. perfect matching	X	1	1	X

5.7 Distance-2 Domination Parameters

Distance-k domination has been fairly well studied; the reader is referred to the chapter on distance domination by Henning in [403]. However, distance-2 domination is particularly interesting in view of the fact that quite a few types of sets that have been studied are distance-2 dominating sets. These include the following:

• 1. all maximal irredundant sets, and there are some 12 varieties that are hereditary,

• 2. a perfect neighborhood set (θ(G));

• 3. a maximal two-packing (ρ(G));

• 4. a minimal external redundant set (er(G));

• 5. a maximal matchable set (μ(G));

• 6. a maximal nearly perfect set;

• 7. a pnc-maximal set;

• 8. a maximal total irredundant set (IR _t(G));

• 9. an R-annihilated set (ra(G)), and

• 10. an R-annihilated and irredundant set (rai(G));

In addition, a variety of types of maximal matchings are also distance-2 edge dominating sets, including:

• 11. a variety of maximal matchings may not produce edge dominating sets, but produce distance-2 edge dominating sets, including a maximal induced matching; a maximal disconnected matching, a maximal acyclic matching; a maximal total matching. The general problem is: how do these types of sets compare as distance-2 dominating sets?

5.8 k-Domatic Number d _k(G)

You are given the problem of assigning to any given vertex v ∈ V  a set of at most k different resources, that is, each vertex has a capacity of storing at most k resources. The resources are chosen from a list of r different resources, where k ≤ r. You must do this in such a way that every vertex has access, in its closed neighborhood, to all r resources. For a given integer k, how large can r be? Denote this by d _k(G). Note that if k = 1, then d ₁(G) = d(G), the domatic number. Thus, we could say that d(G) is the first domatic number, while d ₂(G) is the second domatic number, etc. This resource allocation problem appears in an unpublished technical report by Hedetniemi, Hedetniemi and Wimer in 1987 [384] and recently by Abbas et al. in [1].

5.9 Dominator Colorings

A dominator partition of a graph G is a partition of the vertex set into sets {V ₁, V ₂, …, V _k}, such that every vertex v ∈ V  dominates all of the vertices in at least one block V _i of the partition. The dominator partition number of a graph G equals the smallest order of a dominator partition of G and is denoted Π _d(G). This concept was introduced and studied by Hedetniemi et al. [399].

In this paper the authors observed the following interesting result:

Theorem 4

For any graph G, γ(G) ≤ Π _d(G) ≤ γ(G) + 1.

At the end of this paper, they observed that if you stipulate that every vertex v ∈ V  must dominate all of the vertices in at least one block V _i of the partition, other than its own block, then what you get is called a total dominator partition. You also get the following result, where Π _td(G) is the total dominator partition number and γ _t(G) is the total domination number of a graph G.

Theorem 5

For any graph G, γ _t(G) ≤ Π _td(G) ≤ γ _t(G) + 1.

Total dominator partitions are studied in [406, 449,450,451].

Furthermore, if you stipulate that every block V _i of the partition be an independent set, i.e. that the partition is a proper coloring, then you define what is called a dominator coloring of G. The dominator coloring number χ _d(G) equals the minimum order of a dominator coloring of G. Gera, Rasmussen and Horton have produced the first paper on dominator colorings [286].

But so far what has eluded us is the hoped-for linear algorithm for determining the dominator coloring number, or dominator chromatic number χ _d(T) of any tree T.

5.10 Edge Degree Sequences

We often speak of the vertex degree sequence of a graph G of order n, d ₁ ≥ d ₂ ≥… ≥ d _n. But in this glossary we say nothing about the edge degree sequence, deg(e ₁) ≥ deg(e ₂) ≥… ≥ deg(e _m). These integer sequences are just the vertex degree sequences of line graphs of graphs. But since line graphs form a proper subfamily of the family of all graphs, these edge degree sequences are different. By the edge degree, we mean deg(uv) = deg(u) + deg(v) − 2. What can you say about edge degree sequences of graphs?

5.11 Edge-Vertex Connectivity λ _v(G) and Vertex-Edge Connectivity κ _e(G)

The definitions of vertex connectivity and edge connectivity in Section 3.2 suggest the following. Let S ⊂ V  be a vertex cutset. Recall the definition that a vertex cutset is a set S ⊂ V  in a connected graph whose removal results in a graph which is either not connected or consists of a single vertex. Thus, when the vertices in a cutset S are removed, all edges which are incident with a vertex in S are also removed. Let λ _v(G) equal the minimum number of edges incident with a vertex in a vertex cutset of G.

If F ⊂ E is an edge cutset of a graph G, then when the edges in F are removed, resulting in a disconnected graph G − F, all vertices incident with an edge in F will have their degrees reduced. Let κ _e(G) equal the minimum number of vertices incident with an edge in an edge cutset of G.

5.12 Flower Number flower(G) and Petal Number petal(G)

The definition of the cycle number cycle(v) in Section 3.2, as the number of distinct cycles containing vertex v, suggests that one define the petal number petal(G) of a graph G to be maximum number of cycles k in a set C ₁, C ₂, …, C _k, having the property that for any i ≠ j, C _i ∩ C _j = {v}, that is, these cycles are pairwise vertex disjoint except for having vertex v in common. Each cycle in such a collection is called a petal, and the union of all such cycles defines a flower, the petals of which are centered at v. These subgraphs have applications in distribution networks, in which the central vertex is called a hub and the cycles represent circular routes taken by vehicles, delivering items from the hub and picking up items to be taken back to the hub. Given this, one can define the flower number flower(G) of a graph G to equal the maximum order of a flower subgraph of G, and the petal number petal(G) to equal the maximum number of petals in a flower of G.

5.13 Spider Number spider(G)

A spider is a tree which consists of a collection of paths which are pairwise vertex disjoint, except for having exactly one vertex v in common. These subgraphs have applications in distribution networks, in which the vertex v is called a hub and the paths represent routes taken by vehicles; each vehicle travels from the hub to all of the vertices along the path, delivering items from the hub, and returns from the end of the path, picking up items to be taken back to the hub along the same path. Given this, one could define the spider number spider(G) to equal the maximum order of a (not necessarily induced) spider subgraph in G.

5.14 Four Color Theorems

Arguably the most famous theorem in all of graph theory is the Four Color Theorem, about which volumes have been written. From the perspective of parameters of graphs, the chromatic number χ(G) is a parameter whose largest value over the infinite class of planar graphs is 4, that is, for any planar graph G, χ(G) ≤ 4.

In Sections 3.5 and 3.7 of this Glossary, we have listed and defined about 65 decomposition, partition and coloring parameters of graphs, where we have assumed that graphs are simple, undirected, and have no loops or multiple edges. Consider doing the following: (1) list all 65 such parameters, (2) for each parameter, say generically ρ(G), ask: does there exist a finite constant k, such that for any planar graph G, ρ(G) ≤ k?

For example, the Grundy number, Γr(G) of a tree can be arbitrarily large, and therefore, so can the partial Grundy number ∂Γr(G), the achromatic number, ψ(G), and the pseudoachromatic number, ψ _s(G). Thus, when restricted to planar graphs, none of these coloring parameters can be bounded above by a constant.

As another example, we have seen that for the infinite square grid graphs, which of course are planar, the packing chromatic number is bounded between 13 and 15. Does the packing chromatic number have a constant upper bound for the class of planar graphs? Another interesting example is the b-chromatic number; is this number at most 4 for planar graphs?

In Sections 3.6 and 3.7, we define several numbers that are lower bounds for the chromatic number χ(G). From the Four Color Theorem we know that for any planar graph G, χ(G) ≤ 4, and therefore, each of these numbers is at most 4 for planar graphs. But can you prove directly, without using the Four Color Theorem, that any of the following numbers are at most 4 for planar graphs?

• 1. the co-chromatic number, z(G) ≤ χ(G), each color class is either a clique or an independent set.

• 2. the sub-chromatic number, χ _s(G) ≤ χ(G), each color class is a union of cliques.

• 3. the iterated domination number, γ ^∗(G) ≤ χ(G), each color class is a minimal dominating set in the graph remaining after removing all previous color classes.

• 4. the iterated irredundance number, ir ^∗(G) ≤ χ(G), each color class is a maximal irredundant set in the graph remaining after removing all previous color classes.

• 5. the k-dependent chromatic number, for any fixed k, χ _≤k(G) ≤ χ(G), each color class is a k-dependent set.

• 6. the irredundant chromatic number, χ _irr(G) ≤ χ(G), each color class is a, not necessarily maximal, irredundant set.

• 7. forest arboricity, χ _F(G) ≤ χ(G), each color class is an induced forest of trees.

• 8. path arboricity, χ _P(G) ≤ χ(G), each color class is an induced forest of paths.

• 9. star arboricity, χ _∗(G) ≤ χ(G), each color class is an induced forest of stars.

• 10. spider arboricity, χ _S(G) ≤ χ(G), each color class is an induced forest of spiders.

5.15 Generalized Irredundant Sets

In 1999, Cockayne [158] introduced many new kinds of generalized irredundant sets, but perhaps the most interesting ones are the 12 types of irredundant sets that are hereditary, meaning that every subset of a given type of irredundant set, is also an irredundant set of the same type. Let S denote that a vertex has itself as a private neighbor; let I denote that a vertex has an internal private neighbor, and let E denote that a vertex has an external private neighbor, all with respect to some set S. Consider the following 12 types of irredundant sets, that is let IR _i(G) equal the maximum cardinality set S having each of the following properties with regard to private neighbors for the elements of S.

• 1. IR ₁[S ∧ E] ……….independent open irredundant sets

• 2. IR ₃[S] ……………..independent sets

• 3. IR ₅[(S ∨ I) ∧ E]

• 4. IR ₇[S ∨ (I ∧ E)]

• 5. IR ₉[(S ∧ E) ∨ (I ∧¬E)]

• 6. IR ₁₁[S ∨ (I ∧¬E)]

• 7. IR ₁₃[(S ∧ E) ∨ I]

• 8. IR ₁₅[S ∨ I] ………1-dependent sets

• 9. IR ₂₁[E] ……………open irredundant sets

• 10. IR ₂₃[S ∨ E] ………irredundant sets

• 11. IR ₂₉[I ∨ E] ………….open-open irredundant sets

• 12. IR ₃₁[S ∨ I ∨ E] …….closed-open irredundant sets

Cockayne points out the following inequalities between various of these irredundance parameters.

Theorem 6

For any graph G,

• 1. IR ₁ ≤ IR ₅ ≤ IR ₂₁

• 2. IR ₉ ≤ IR ₁₃ ≤ IR ₂₉

• 3. IR ₃ ≤ IR ₇ ≤ IR ₂₃

• 4. IR ₁₁ ≤ IR ₁₅ ≤ IR ₃₁

• 5. IR ₁ ≤ IR ₃ ≤ IR ₁₁

• 6. IR ₁ ≤ IR ₉ ≤ IR ₁₁

• 7. IR ₅ ≤ IR ₇ ≤ IR ₁₅

• 8. IR ₅ ≤ IR ₁₃ ≤ IR ₁₅

• 9. IR ₂₁ ≤ IR ₂₃ ≤ IR ₃₁

• 10. IR ₂₁ ≤ IR ₂₉ ≤ IR ₃₁

Taken together, these parameters define a 2 × 3 × 2 cube of inequalities, or in other words, they form the prism consisting of two parallel copies of a 2 × 3 grid.

Irredundant sets of types 5, 7, 9, 11, and 13 have not been studied.

5.16 Hall Ratios

The Hall Ratio of a graph G is defined to equal max{|V (H)|∕α(H) : H a subgraph of G}, where α(G) is the vertex independence number of a graph G. This ratio was first introduced by Hilton and Johnson in 1990 [416], and is related to the study of the chromatic number and list colorings of graphs. But the Hall ratio is really quite generic, and brings to mind other ratios, like the binding number and toughness. This suggests that it might be worthwhile to consider the ratios of any number of parameters to the orders of a graph.

5.17 Hamiltonian Bottleneck Number hbn(G)

The definition of the Hamiltonian number h(G) in Section 3.3 suggests the following. Let c = v ₁, v ₂, …, v _n, v _n+1 = v ₁ be a cyclic ordering of the vertices of a graph G. Let the Hamiltonian bottleneck number of a cyclic ordering c be hbn(c) = max{d(v _i, v _i+1) : 1 ≤ i ≤ n}, that is, hbn(c) equals the maximum distance between two consecutive vertices of c. The Hamiltonian bottleneck number is hbn(G) = min{hbn(c) : c a cyclic ordering of V }. It follows immediately that hbn(G) = 1 if and only if G is Hamiltonian. The same parameter can be considered for linear orderings l = v ₁, v ₂, …, v _n of the vertices of graphs of order n, in which case one is considering Hamiltonian paths, and one can define the Hamiltonian path bottleneck number hpbn(G). Obviously, hpbn(G) = 1 if and only if G has a Hamiltonian path. In 1964, Sekanina [564] asked, in effect, for which graphs G is hpbn(G) = 2? The author states: “For trees this problem was solved in a paper of F. Neuman, to appear in Čas. Pěst. Mat.”; however, we have not been able to find such a paper. It appears that the graphs for which hbn(G) = 2 are those graphs G whose square G ² is Hamiltonian, and these graphs have been studied.

5.18 Minimaximal Path Number mmp(G) and Minimaximal Trail Number mmt(G)

The definition of the trail number in Section 3.3 suggests the following. Recall that a trail is a walk having no repeated edges. A path or a trail is maximal if its length cannot be increased by the addition of an edge at either end. It does not appear that the minimum length of a maximal path mmp(G) or the minimum length of a maximal trail mmt(G) have been studied.

5.19 New Inequality Chains from Hereditary and Super-Hereditary Properties

The well-studied domination chain is the following:

$$\displaystyle \begin{aligned}er(G) \leq ir(G) \leq \gamma(G) \leq i(G) \leq \alpha(T) \leq \varGamma(T) \leq IR(G) \leq ER(G).\end{aligned}$$

where

• er(G) and ER(G) denote the lower and upper external redundance numbers,

• ir(G) and IR(G) denote the lower and upper irredundance numbers,

• γ(G) and Γ(G) denote the lower and upper domination numbers, and

• i(G) and α(G) denote the independent domination number and the independence number.

We think we understand why these inequality chains exist. For example, independence is a hereditary property, domination is a superhereditary property, and irredundance is a hereditary property. But we do not understand why external redundance is not a superhereditary property.

Thus, in order to figure this out, we think it would be a good idea to study several other inequality chains. The idea is simple.

Start with any hereditary property P ₁. Then define two parameters: the minimum cardinality of a maximal P ₁-set and the maximum cardinality of a P ₁-set, say β ₁(G) and α ₁(G), respectively.

Next, use the maximality condition of a P ₁-set to define a second property P ₂. This property P ₂ should be super-hereditary. Use this property to define two new parameters: the minimum cardinality of a P ₂-set and the maximum cardinality of a minimal P ₂-set, say β ₂(G) and α ₂(G), respectively.

At this point it should be the case that: β ₂(G) ≤ β ₁(G) ≤ α ₁(G) ≤ α ₂(G).

Now, continue in the same way. Use the minimality condition of a P ₂-set to define a third property P ₃. This property should be hereditary. Use this property to define two new parameters: the minimum cardinality of a maximal P ₃-set and the maximum cardinality of a P ₃-set, say β ₃(G) and α ₃(G), respectively.

At this point it should be the case that:

$$\displaystyle \begin{aligned} \beta_3(G) \leq \beta_2(G) \leq \beta_1(G) \leq \alpha_1(G) \leq \alpha_2(G) \leq \alpha_3(G).\end{aligned} $$

As we said, you can start to build such an inequality chain with any hereditary property. Examples of hereditary properties of sets S ⊆ V  include the following, where G[S] denotes the subgraph induced by S:

• 1. G[S] is acyclic,

• 2. S is k-dependent, i.e. the maximum degree Δ(G[S]) ≤ k,

• 3. S is a packing,

• 4. G[S] is bipartite,

• 5. S is matchable,

• 6. S is irredundant, open irredundant, open-open irredundant, etc.,

• 7. S is a restrained set, i.e. for every u ∈ (V − S), N(u) ∩ (V − S) ≠ ∅, or

• 8. S is enclaveless, i.e. for every u ∈ S, N(u) ∩ (V − S) ≠ ∅.

We should also point out that one can start an inequality chain with a super-hereditary property just as well. Examples of super-hereditary properties include:

• 1. G[S] contains a cycle,

• 2. Δ(G[S]) ≥ k,

• 3. S is a dominating set,

• 4. S is a total dominating set,

• 5. S is a strong dominating set,

• 6. S is an internally strong dominating set,

• 7. S is a vertex cover,

• 8. S is a global offensive alliance,

• 9. S is a distance-k dominating set,

• 10. S is a P ₃-dominating set,

• 11. S is a capacity-k dominating set.

5.20 New Max and Min Domination Parameters

Subramanian [596], and later Arumugam and Subramanian [20] introduced an independence idea that spawns a whole host of new parameters.

Define the following for every vertex v ∈ V :

• ir(v) = min {|S|, v ∈ S and S is a maximal irredundant set}

• γ(v) = min {|S|, v ∈ S and S is a minimal dominating set}

• i(v) = min {|S|, v ∈ S and S is a maximal independent dominating set}

• α(v) = max {|S|, v ∈ S and S is an independent set}

• Γ(v) =max {|S|, v ∈ S and S is a minimal dominating set}

• IR(v) = max {|S|, v ∈ S and S is an irredundant set}

Now, over all vertices v ∈ V  define the following:

• irmax(G) = max {ir(v) : v ∈ V }

• γmax(G) = max {γ(v) : v ∈ V }

• imax(G) = max {i(v) : v ∈ V }

• αmin(G) = min {α(v) : v ∈ V }

• Γmin(G) = min {Γ(v) : v ∈ V }

• IRmin(G) = min {IR(v) : v ∈ V }

The following inequalities follow from these definitions:

Proposition 1

For any graph G,

• (i) ir(G) ≤ irmax(G)

• (ii) γ(G) ≤ γmax(G)

• (iii) i(G) ≤ imax(G)

• (iv) αmin(G) ≤ α(G)

• (v) Γmin(G) ≤ Γ(G)

• (vi) IRmin(G) ≤ IR(G)

These parameters have received very little study.

5.21 P-Matchings and the Independent Matching Number $\alpha ^{\prime }_{ind}(G)$

Let e ₁ = x ₁ y ₁, e ₂ = x ₂ y ₂, …, e _k = x _k y _k be the edges of a matching M, and let X(M) = {x _, x ₂, …, x _k} and Y (M) = {y ₁, y ₂, …, y _k}. We can think of the edges of M as being oriented vertically, with the vertices in X(M) being situated above, or to the north of, the vertices in Y (M) to the south. One can see that V (M) = (X(M), Y (M)) represents one of 2^k possible orientations of the edges of M. We say that a matching M is independent if it has an orientation such that the set X(M) is an independent set. Thus, the independent matching number $\alpha ^{\prime }_{ind}(G)$ equals the maximum cardinality of an independent matching in G. For this parameter, for example, it is not difficult to show that for any nontrivial tree T, $\alpha '(T) = \alpha ^{\prime }_{ind}(T)$.

This, in turn, suggests a broad new concept. A P-matching is a matching M = {x ₁ y ₁, x ₂ y ₂, …, x _k y _k}, such that the set X = {x ₁, x ₂, …, x _k} is a set having property P. There are many properties P of interest. For example, one can define $\alpha ^{\prime }_c(G)$ to equal the maximum cardinality of a connected matching; in this case, there exists a matching M having an orientation V (M) = (X(M), Y (M)) such that the induced subgraph G[X(M)] is connected. Another interesting example are matchings M where the set X(M) is a dominating set, in which case M is a dominating matching, or where the set X(M) ∪ Y (M) is a dominating set. In this case, V (M) = X(M) ∪ Y (M) is a paired dominating set, as defined in Section 3.8.1. Still another interesting case occurs where both sets X(M) and Y (M) are dominating sets; these could be called matched dominating sets.

5.22 P, Q-Matchings

Let P and Q be two properties of sets of vertices. A matching M is called a P, Q-matching if it has an orientation V (M) = (X(M), Y (M)) such that X(M) has property P and Y (M) has property Q. For example, if P = Q and P is the property of being an independent set, then a doubly independent matching is a matching M having an orientation V (M) = (X(M), Y (M)) in which both X(M) an Y (M) are independent sets.

5.23 Regular and Uniformly Regular Colorings

A partition π = {V ₁, V ₂, …, V _k} of the vertices V  of a graph G = (V, E) is called a regular coloring if the subgraph G[V _i] induced by each color class V _i is a regular graph. The regular chromatic number χ _r(G) of a graph G equals the minimum order of a regular coloring of G.

A partition π = {V ₁, V ₂, …, V _k} of the vertices V  of a graph G = (V, E) is called a uniformly regular coloring if the subgraph G[V _i] induced by each color class V _i is a disjoint union of regular graphs. The uniformly regular chromatic number χ _ur(G) of a graph G equals the minimum order of a uniformly regular coloring of G.

Uniformly regular colorings are closely related to what are called sub-chromatic colorings which are defined in Section 3.7. The sub-chromatic number χ _K(G) equals the minimum order of a partition π = {V ₁, V ₂, …, V _k} of the vertices V  of a graph G = (V, E) such that every color class V _i induces a subgraph consisting of a disjoint union of complete subgraphs. Thus, sub-chromatic colorings are uniformly regular colorings, but not conversely.

Proposition 2

For any graph G, χ _ur(G) ≤ χ _r(G) ≤ χ(G).

Can you prove that either χ _ur(G) ≤ 4 or χ _K(G) ≤ 4 for planar graphs G, without appealing to the Four Color Theorem?

5.24 Two Disjoint $\mathcal {P}$-Sets

Hedetniemi et al. [394] considered the minimum cardinality of two disjoint dominating sets in a graph G, called the dual domination number, denoted by γγ(G). It follows, by definition, that 2γ(G) ≤ γγ(G) ≤ γ(G) + γ ⁻¹(G), where γ ⁻¹(G) is the inverse domination number.

One can also define the upper dual domination number, ΓΓ(G), to equal the maximum cardinality of two disjoint minimal dominating sets in a graph G. This parameter was not studied. But there is more. One can define iγ(G) and αγ(G) to equal the minimum and maximum cardinality of an independent dominating set and a disjoint minimal dominating set, respectively. It then follows from all of these definitions that:

$$\displaystyle \begin{aligned}2\gamma(G) \leq \gamma \gamma(G) \leq i \gamma(G) \leq \alpha \varGamma(G) \leq \varGamma \varGamma(G) \leq \leq 2\varGamma(G),\end{aligned}$$

and, in addition, we have:

$$\displaystyle \begin{aligned}ir ir(G) \leq ir \gamma(G) \leq \gamma \gamma(G) \leq i \gamma(G) \leq \alpha \varGamma(G) \leq \varGamma \varGamma(G) \leq \varGamma IR(G) \leq IR IR(G).\end{aligned}$$

None of these parameters, other than γγ(G), appear to have been studied.

5.25 Uniformly Strong Sets

In [440], Kamath and Bhat define a vertex v in a graph G = (V, E) to be strong if deg(v) ≥ deg(u) for every vertex u adjacent to v. Similarly, a vertex is called weak if deg(v) ≤ deg(u) for every vertex u adjacent to v. These two definitions suggest a variety of new things that can be studied.

Let us define a set S ⊆ V  to be uniformly strong if every vertex u ∈ S is a strong vertex in the induced subgraph G[S]. The maximum cardinality of a uniformly strong set is called the uniformly strong number of a graph G and is denoted S(G). Similarly, the minimum cardinality of a maximal uniformly strong set S, denoted s(G), is called the lower uniformly strong number of G.

Notice that uniformly strong sets are essentially sets S such that the induced subgraph G[S] consists of a disjoint union of regular graphs. Note that the property of being a strong set is neither hereditary nor super-hereditary. The following results follow immediately from the definitions.

Proposition 3

For any regular graph G of order n, s(G) = S(G) = n.

Recall that α(G), the independence number of G, equals the maximum cardinality of an independent set in G. Similarly, α ¹(G) is the 1-dependence number, i.e. the maximum cardinality of a set S such that Δ(G[S]) ≤ 1. Similarly, i(G) equals the minimum cardinality of a maximal independent set in G (also called the independent domination number), while i ¹(G), the lower 1-dependence number, equals the minimum cardinality of a maximal 1-dependent set in G.

Notice that the subgraphs induced by maximal 1-dependent sets are just disjoint unions of K ₁’s and K ₂’s. Thus, they are strong sets.

Proposition 4

For any graph G of order n,

$$\displaystyle \begin{aligned}s(G) \leq i^1(G) \leq i(G) \leq \alpha_0(G) \leq \alpha^1(G) \leq S(G) \leq n.\end{aligned}$$

Proposition 5

For any tree T, S(T) = α ¹(T).

What can you say about the values of s(G) and S(G)?

6 Conclusions

In this glossary we have enumerated some 300 parameters commonly used in graph theory, and for many of these we have presented related conjectures. We also listed several new suggested parameters and open problems. While many of the numbers listed in the glossary and still other parameters have been discussed in other comprehensive books, we feel this is the most comprehensive glossary ever assembled of graph theory parameters. Within the given time and page limitations for producing this glossary, we have annotated many of these parameters with basic properties, results, and conjectures about them, in order to provide a clearer understanding of these parameters beyond their mere definition.

No attempt has been made in this glossary of parameters and related conjectures to be complete. Indeed, it would be a formidable task to construct a complete listing. Furthermore, no attempt has been made to provide a complete bibliography of the publications in which these parameters first appeared or have been studied.

But with an eye toward the creation of future areas of research in graph theory, and their corresponding new parameters, let us close with this thought. Consider each of the following five combinatorial optimization problems, all found in the classic NP-completeness book by Garey and Johnson [281], which is well-known to researchers in graph algorithms and complexity. Each of these five problems has become a well-known, basic NP-complete decision problem.

[SP3] Set Packing

Given a collection S of finite sets and a positive integer k ≤|S|, does S contain at least k mutually disjoint sets?

[SP4] Set Splitting

Given a collection S of subsets of a finite set S, is there a bipartition S = {S ₁, S ₂} of S, such that no subset in S is contained entirely in S ₁ or S ₂?

[SP5] Minimum Cover

Given a collection S of finite subsets of a set S, and a positive integer k ≤|S|, does S contain a cover for S of cardinality at most k? that is, a subset S′⊆S where |S′|≤ k and every element of S belongs to at least one member of S′?

[SP6] Minimum Test Set

Given a collection S of finite subsets of a set S, and a positive integer k ≤|S|, does S contain a subset S′⊆S of cardinality at most k, such that for every u, v ∈ S there is at least one set in S’ that contains exactly one of u and v?

[SP7] Set Basis

Given a collection S of finite subsets of a set S, and a positive integer k ≤|S|, is there a collection B of k subsets of S such that for each set S” ∈S there is a sub-collection of B whose union is precisely S”?

Each of these five general set problems has many instances when applied to graphs G = (V, E). First of all, one can speak of the families of sets of vertices in (1) open neighborhoods, (2) closed neighborhoods, (3) paths, (4) induced paths, (5) cycles, (6) induced cycles, (7) complete subgraphs, (8) independent sets, or maximal independent sets, and (9) dominating sets or minimal dominating sets, and many, many more instances.

Next, one can speak of the families of sets of edges in similar sets, e.g. paths, induced paths, cycles, induced cycles, cliques and independent sets of edges, but including the sets of edges E(v) incident to a given vertex v or the sets of edges defining a spanning tree, and many, many more instances.

With each instance of any one of these five general problem types, there will be corresponding minimum, maximum, mini-maximal or maxi-minimal parameters.

Thus, this glossary not only provides a fairly comprehensive collection of parameters that have been defined and studied, but provides many ideas for the discovery and future study of parameters.