Graph power

Last updated • 3 min readFrom Wikipedia, The Free Encyclopedia
The square of a graph Square of a graph.svg
The square of a graph

In graph theory, a branch of mathematics, the kth powerGk of an undirected graph G is another graph that has the same set of vertices, but in which two vertices are adjacent when their distance in G is at most k. Powers of graphs are referred to using terminology similar to that of exponentiation of numbers: G2 is called the square of G, G3 is called the cube of G, etc. [1]

Contents

Graph powers should be distinguished from the products of a graph with itself, which (unlike powers) generally have many more vertices than the original graph.

Properties

If a graph has diameter d, then its d-th power is the complete graph. [2] If a graph family has bounded clique-width, then so do its d-th powers for any fixed d. [3]

Coloring

Graph coloring on the square of a graph may be used to assign frequencies to the participants of wireless communication networks so that no two participants interfere with each other at any of their common neighbors, [4] and to find graph drawings with high angular resolution. [5]

Both the chromatic number and the degeneracy of the kth power of a planar graph of maximum degree Δ are O(Δ⌊k/2⌋), where the degeneracy bound shows that a greedy coloring algorithm may be used to color the graph with this many colors. [4] For the special case of a square of a planar graph, Wegner conjectured in 1977 that the chromatic number of the square of a planar graph is at most max(Δ + 5, 3Δ/2 + 1), and it is known that the chromatic number is at most 5Δ/3 + O(1). [6] [7] More generally, for any graph with degeneracy d and maximum degree Δ, the degeneracy of the square of the graph is O(dΔ), so many types of sparse graph other than the planar graphs also have squares whose chromatic number is proportional to Δ.

Although the chromatic number of the square of a nonplanar graph with maximum degree Δ may be proportional to Δ2 in the worst case, it is smaller for graphs of high girth, being bounded by O(Δ2 / log Δ) in this case. [8]

Determining the minimum number of colors needed to color the square of a graph is NP-hard, even in the planar case. [9]

Hamiltonicity

The cube of every connected graph necessarily contains a Hamiltonian cycle. [10] It is not necessarily the case that the square of a connected graph is Hamiltonian, and it is NP-complete to determine whether the square is Hamiltonian. [11] Nevertheless, by Fleischner's theorem, the square of a 2-vertex-connected graph is always Hamiltonian. [12]

Computational complexity

The kth power of a graph with n vertices and m edges may be computed in time O(mn) by performing a breadth first search starting from each vertex to determine the distances to all other vertices, or slightly faster using more sophisticated algorithms. [13] Alternatively, If A is an adjacency matrix for the graph, modified to have nonzero entries on its main diagonal, then the nonzero entries of Ak give the adjacency matrix of the kth power of the graph, [14] from which it follows that constructing kth powers may be performed in an amount of time that is within a logarithmic factor of the time for matrix multiplication.

The kth powers of trees can be recognized in time linear in the size of the input graph. [15]

Given a graph, deciding whether it is the square of another graph is NP-complete. [16] Moreover, it is NP-complete to determine whether a graph is a kth power of another graph, for a given number k ≥ 2, or whether it is a kth power of a bipartite graph, for k > 2. [17]

Induced subgraphs

K4 as the half-square of a cube graph Demi-3-cube.svg
K4 as the half-square of a cube graph

The half-square of a bipartite graph G is the subgraph of G2 induced by one side of the bipartition of G. Map graphs are the half-squares of planar graphs, [18] and halved cube graphs are the half-squares of hypercube graphs. [19]

Leaf powers are the subgraphs of powers of trees induced by the leaves of the tree. A k-leaf power is a leaf power whose exponent is k. [20]

Related Research Articles

The Hamiltonian path problem is a topic discussed in the fields of complexity theory and graph theory. It decides if a directed or undirected graph, G, contains a Hamiltonian path, a path that visits every vertex in the graph exactly once. The problem may specify the start and end of the path, in which case the starting vertex s and ending vertex t must be identified.

<span class="mw-page-title-main">Outerplanar graph</span> Non-crossing graph with vertices on outer face

In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing.

<span class="mw-page-title-main">Graph coloring</span> Methodic assignment of colors to elements of a graph

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

In graph theory, a uniquely colorable graph is a k-chromatic graph that has only one possible (proper) k-coloring up to permutation of the colors. Equivalently, there is only one way to partition its vertices into k independent sets and there is no way to partition them into k − 1 independent sets.

<span class="mw-page-title-main">Edge coloring</span> Problem of coloring a graphs edges such that meeting edges do not match

In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

In graph theory, a branch of mathematics, list coloring is a type of graph coloring where each vertex can be restricted to a list of allowed colors. It was first studied in the 1970s in independent papers by Vizing and by Erdős, Rubin, and Taylor.

<span class="mw-page-title-main">Acyclic coloring</span> Graph coloring in which all 2-chromatic subgraphs are acyclic

In graph theory, an acyclic coloring is a (proper) vertex coloring in which every 2-chromatic subgraph is acyclic. The acyclic chromatic numberA(G) of a graph G is the fewest colors needed in any acyclic coloring of G.

<span class="mw-page-title-main">Grundy number</span> Maximum number of colors obtainable by a greedy graph coloring algorithm

In graph theory, the Grundy number or Grundy chromatic number of an undirected graph is the maximum number of colors that can be used by a greedy coloring strategy that considers the vertices of the graph in sequence and assigns each vertex its first available color, using a vertex ordering chosen to use as many colors as possible. Grundy numbers are named after P. M. Grundy, who studied an analogous concept for directed graphs in 1939. The undirected version was introduced by Christen & Selkow (1979).

In graph theory, Vizing's theorem states that every simple undirected graph may be edge colored using a number of colors that is at most one larger than the maximum degree Δ of the graph. At least Δ colors are always necessary, so the undirected graphs may be partitioned into two classes: "class one" graphs for which Δ colors suffice, and "class two" graphs for which Δ + 1 colors are necessary. A more general version of Vizing's theorem states that every undirected multigraph without loops can be colored with at most Δ+µ colors, where µ is the multiplicity of the multigraph. The theorem is named for Vadim G. Vizing who published it in 1964.

<span class="mw-page-title-main">Triangle-free graph</span> Graph without triples of adjacent vertices

In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally independent graphs.

<span class="mw-page-title-main">Halin graph</span> Mathematical tree with cycle through leaves

In graph theory, a Halin graph is a type of planar graph, constructed by connecting the leaves of a tree into a cycle. The tree must have at least four vertices, none of which has exactly two neighbors; it should be drawn in the plane so none of its edges cross, and the cycle connects the leaves in their clockwise ordering in this embedding. Thus, the cycle forms the outer face of the Halin graph, with the tree inside it.

<span class="mw-page-title-main">Star coloring</span> Graph coloring in which every 4-vertex path uses ≥3 colors

In the mathematical field of graph theory, a star coloring of a graph G is a (proper) vertex coloring in which every path on four vertices uses at least three distinct colors. Equivalently, in a star coloring, the induced subgraphs formed by the vertices of any two colors has connected components that are star graphs. Star coloring has been introduced by Grünbaum (1973). The star chromatic number of G is the fewest colors needed to star color G.

<span class="mw-page-title-main">Greedy coloring</span> One-by-one assignment of colors to graph vertices

In the study of graph coloring problems in mathematics and computer science, a greedy coloring or sequential coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence and assigns each vertex its first available color. Greedy colorings can be found in linear time, but they do not, in general, use the minimum number of colors possible.

In graph theory, an area of mathematics, an equitable coloring is an assignment of colors to the vertices of an undirected graph, in such a way that

In the mathematical area of graph theory, an undirected graph G is strongly chordal if it is a chordal graph and every cycle of even length in G has an odd chord, i.e., an edge that connects two vertices that are an odd distance (>1) apart from each other in the cycle.

<span class="mw-page-title-main">Degeneracy (graph theory)</span> Measurement of graph sparsity

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

<span class="mw-page-title-main">Pancyclic graph</span>

In the mathematical study of graph theory, a pancyclic graph is a directed graph or undirected graph that contains cycles of all possible lengths from three up to the number of vertices in the graph. Pancyclic graphs are a generalization of Hamiltonian graphs, graphs which have a cycle of the maximum possible length.

<span class="mw-page-title-main">Adjacent-vertex-distinguishing-total coloring</span> Type of total coloring in graph theory

In graph theory, a total coloring is a coloring on the vertices and edges of a graph such that:

The graph coloring game is a mathematical game related to graph theory. Coloring game problems arose as game-theoretic versions of well-known graph coloring problems. In a coloring game, two players use a given set of colors to construct a coloring of a graph, following specific rules depending on the game we consider. One player tries to successfully complete the coloring of the graph, when the other one tries to prevent him from achieving it.

In graph theory, the act of coloring generally implies the assignment of labels to vertices, edges or faces in a graph. The incidence coloring is a special graph labeling where each incidence of an edge with a vertex is assigned a color under certain constraints.

References

  1. ↑ Bondy, Adrian; Murty, U. S. R. (2008), Graph Theory, Graduate Texts in Mathematics, vol. 244, Springer, p. 82, ISBN   9781846289699 .
  2. ↑ Weisstein, Eric W., "Graph Power", MathWorld
  3. ↑ Todinca, Ioan (2003), "Coloring powers of graphs of bounded clique-width", Graph-theoretic concepts in computer science, Lecture Notes in Comput. Sci., vol. 2880, Springer, Berlin, pp. 370–382, doi:10.1007/978-3-540-39890-5_32, MR   2080095 .
  4. 1 2 Agnarsson, Geir; Halldórsson, Magnús M. (2000), "Coloring powers of planar graphs", Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '00), San Francisco, California, USA, pp. 654–662{{citation}}: CS1 maint: location missing publisher (link).
  5. ↑ Formann, M.; Hagerup, T.; Haralambides, J.; Kaufmann, M.; Leighton, F. T.; Symvonis, A.; Welzl, E.; Woeginger, G. (1993), "Drawing graphs in the plane with high resolution", SIAM Journal on Computing , 22 (5): 1035–1052, doi:10.1137/0222063, MR   1237161 .
  6. ↑ Kramer, Florica; Kramer, Horst (2008), "A survey on the distance-colouring of graphs", Discrete Mathematics , 308 (2–3): 422–426, doi: 10.1016/j.disc.2006.11.059 , MR   2378044 .
  7. ↑ Molloy, Michael; Salavatipour, Mohammad R. (2005), "A bound on the chromatic number of the square of a planar graph", Journal of Combinatorial Theory , Series B, 94 (2): 189–213, doi:10.1016/j.jctb.2004.12.005, hdl: 1807/9473 , MR   2145512 .
  8. ↑ Alon, Noga; Mohar, Bojan (2002), "The chromatic number of graph powers", Combinatorics, Probability and Computing , 11 (1): 1–10, doi:10.1017/S0963548301004965, MR   1888178, S2CID   2706926 .
  9. ↑ Agnarsson & Halldórsson (2000) list publications proving NP-hardness for general graphs by McCormick (1983) and Lin and Skiena (1995), and for planar graphs by Ramanathan and Lloyd (1992, 1993).
  10. ↑ Bondy & Murty (2008), p. 105.
  11. ↑ Underground, Polly (1978), "On graphs with Hamiltonian squares", Discrete Mathematics , 21 (3): 323, doi: 10.1016/0012-365X(78)90164-4 , MR   0522906 .
  12. ↑ Diestel, Reinhard (2012), "10. Hamiltonian cycles", Graph Theory (PDF) (corrected 4th electronic ed.).
  13. ↑ Chan, Timothy M. (2012), "All-pairs shortest paths for unweighted undirected graphs in time", ACM Transactions on Algorithms, 8 (4): A34:1–A34:17, doi:10.1145/2344422.2344424, MR   2981912, S2CID   1212001
  14. ↑ Hammack, Richard; Imrich, Wilfried; Klavžar, Sandi (2011), Handbook of Product Graphs, Discrete Mathematics and Its Applications (2nd ed.), CRC Press, p. 94, ISBN   9781439813058 .
  15. ↑ Chang, Maw-Shang; Ko, Ming-Tat; Lu, Hsueh-I (2015), "Linear-Time Algorithms for Tree Root Problems", Algorithmica , 71 (2): 471–495, doi:10.1007/s00453-013-9815-y, S2CID   253971732 .
  16. ↑ Motwani, R.; Sudan, M. (1994), "Computing roots of graphs is hard", Discrete Applied Mathematics , 54: 81–88, doi: 10.1016/0166-218x(94)00023-9 .
  17. ↑ Le, Van Bang; Nguyen, Ngoc Tuy (2010), "Hardness results and efficient algorithms for graph powers", Graph-Theoretic Concepts in Computer Science: 35th International Workshop, WG 2009, Montpellier, France, June 24-26, 2009, Revised Papers, Lecture Notes in Computer Science, vol. 5911, Berlin: Springer, pp. 238–249, doi:10.1007/978-3-642-11409-0_21, ISBN   978-3-642-11408-3, MR   2587715 .
  18. ↑ Chen, Zhi-Zhong; Grigni, Michelangelo; Papadimitriou, Christos H. (2002), "Map graphs", Journal of the ACM , 49 (2): 127–138, arXiv: cs/9910013 , doi:10.1145/506147.506148, MR   2147819, S2CID   2657838 .
  19. ↑ Shpectorov, S. V. (1993), "On scale embeddings of graphs into hypercubes", European Journal of Combinatorics , 14 (2): 117–130, doi: 10.1006/eujc.1993.1016 , MR   1206617 .
  20. ↑ Nishimura, N.; Ragde, P.; Thilikos, D.M. (2002), "On graph powers for leaf-labeled trees", Journal of Algorithms , 42: 69–108, doi:10.1006/jagm.2001.1195 .
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.