GRAPH ENUMERATIONS

 

Enumeration[edit]

There is a large literature on graphical enumeration: the problem of counting graphs meeting specified conditions. Some of this work is found in Harary and Palmer (1973).

Subgraphs, induced subgraphs, and minors[edit]

A common problem, called the subgraph isomorphism problem, is finding a fixed graph as a subgraph in a given graph. One reason to be interested in such a question is that many graph properties are hereditary for subgraphs, which means that a graph has the property if and only if all subgraphs have it too. Unfortunately, finding maximal subgraphs of a certain kind is often an NP-complete problem. For example:

  • Finding the largest complete subgraph is called the clique problem (NP-complete).

One special case of subgraph isomorphism is the graph isomorphism problem. It asks whether two graphs are isomorphic. It is not known whether this problem is NP-complete, nor whether it can be solved in polynomial time.

A similar problem is finding induced subgraphs in a given graph. Again, some important graph properties are hereditary with respect to induced subgraphs, which means that a graph has a property if and only if all induced subgraphs also have it. Finding maximal induced subgraphs of a certain kind is also often NP-complete. For example:

Still another such problem, the minor containment problem, is to find a fixed graph as a minor of a given graph. A minor or subcontraction of a graph is any graph obtained by taking a subgraph and contracting some (or no) edges. Many graph properties are hereditary for minors, which means that a graph has a property if and only if all minors have it too. For example, Wagner's Theorem states:

A similar problem, the subdivision containment problem, is to find a fixed graph as a subdivision of a given graph. A subdivision or homeomorphism of a graph is any graph obtained by subdividing some (or no) edges. Subdivision containment is related to graph properties such as planarity. For example, Kuratowski's Theorem states:

Another problem in subdivision containment is the Kelmans–Seymour conjecture:

Another class of problems has to do with the extent to which various species and generalizations of graphs are determined by their point-deleted subgraphs. For example:

Graph coloring[edit]

Main article: Graph coloring

Many problems and theorems in graph theory have to do with various ways of coloring graphs. Typically, one is interested in coloring a graph so that no two adjacent vertices have the same color, or with other similar restrictions. One may also consider coloring edges (possibly so that no two coincident edges are the same color), or other variations. Among the famous results and conjectures concerning graph coloring are the following:

Subsumption and unification[edit]

Constraint modeling theories concern families of directed graphs related by a partial order. In these applications, graphs are ordered by specificity, meaning that more constrained graphs—which are more specific and thus contain a greater amount of information—are subsumed by those that are more general. Operations between graphs include evaluating the direction of a subsumption relationship between two graphs, if any, and computing graph unification. The unification of two argument graphs is defined as the most general graph (or the computation thereof) that is consistent with (i.e. contains all of the information in) the inputs, if such a graph exists; efficient unification algorithms are known.

For constraint frameworks which are strictly compositional, graph unification is the sufficient satisfiability and combination function. Well-known applications include automatic theorem proving and modeling the elaboration of linguistic structure.

Route problems[edit]

Network flow[edit]

There are numerous problems arising especially from applications that have to do with various notions of flows in networks, for example:

Visibility problems[edit]

Covering problems[edit]

Covering problems in graphs may refer to various set cover problems on subsets of vertices/subgraphs.

  • Dominating set problem is the special case of set cover problem where sets are the closed neighborhoods.
  • Vertex cover problem is the special case of set cover problem where sets to cover are every edges.
  • The original set cover problem, also called hitting set, can be described as a vertex cover in a hypergraph.

Decomposition problems[edit]

Decomposition, defined as partitioning the edge set of a graph (with as many vertices as necessary accompanying the edges of each part of the partition), has a wide variety of questions. Often, the problem is to decompose a graph into subgraphs isomorphic to a fixed graph; for instance, decomposing a complete graph into Hamiltonian cycles. Other problems specify a family of graphs into which a given graph should be decomposed, for instance, a family of cycles, or decomposing a complete graph Kn into n − 1 specified trees having, respectively, 1, 2, 3, ..., n − 1 edges.

Some specific decomposition problems that have been studied include:

Graph classes[edit]

Many problems involve characterizing the members of various classes of graphs. Some examples of such questions are below:

Comments

Post a Comment

Popular posts from this blog

Introduction to Complex analysis

complex analaysis  is a branch of mathematics that deals with complex numbers, their functions, and their calculus. In simple terms, complex analysis is an extension of the calculus of real numbers to the complex domain. We will extend the notions of continuity, derivatives, and integrals, familiar from calculus to the case of complex functions of a complex variable. In doing so we will come across analytic functions, which form the centerpiece of this introduction. In fact, to a large extent complex analysis is the study of analytic functions. The basic ingredient of complex analysis is an analytic function, or that we know so well in calculus as a differentiable function. Any  complex number   z  can be thought of as a point in a plane ( x,y ), so  z = x+iy,  where  i=√-1.   In a similar fashion, any complex function of a complex variable  z  can be separated into two functions, as in,   f(z)=u(z)+iv(z),  or,  f(x,y...
Read more

Conformal mapping

Image
  Applications of conformal mapping [ edit ] This article  is in  list  format but may read better as  prose .  You can help by  converting this article , if appropriate.  Editing help  is available.   ( August 2022 ) In aerospace engineering [2] In biomedical sciences [3] In brain mapping [4] Genetic mapping [5] [6] [7] Geodesics [8] In geometry [9] In geophysics [10] In Google [11] [12] In engineering [13] [14] In electronics [15] In geography [16]  and cartography. [17] Major results [ edit ] Color wheel graph  of the function  f ( x ) =  ( x 2  − 1)( x  − 2 −  i ) 2 / x 2  + 2 + 2 i . Hue  represents the  argument ,  brightness  the  magnitude. One of the central tools in complex analysis is the  line integral . The line integral around a closed path of a function that is holomorphic everywhere inside the area bounded by the closed path is always zero, as is stated...
Read more

Groups

  Groups Main article:  Group (mathematics) See also:  Group theory  and  Examples of groups Combining the above concepts gives one of the most important structures in mathematics: a  group . A group is a combination of a set  S  and a single  binary operation  ∗, defined in any way you choose, but with the following properties: An identity element  e  exists, such that for every member  a  of  S ,  e  ∗  a  and  a  ∗  e  are both identical to  a . Every element has an inverse: for every member  a  of  S , there exists a member  a −1  such that  a  ∗  a −1  and  a −1  ∗  a  are both identical to the identity element. The operation is associative: if  a ,  b  and  c  are members of  S , then ( a  ∗  b ) ∗  c  is identical to  a  ∗ ( b  ∗...
Read more