digplanet beta 1: Athena
Share digplanet:


Applied sciences






















Star network 7.svg
The star S7. (Some authors index this as S8.)
Vertices k+1
Edges k
Diameter minimum of (2, k)
Chromatic number minimum of (2, k + 1)
Chromatic index k
Properties Edge-transitive
Unit distance
Notation Sk

In graph theory, a star Sk is the complete bipartite graph K1,k: a tree with one internal node and k leaves (but, no internal nodes and k + 1 leaves when k ≤ 1). Alternatively, some authors define Sk to be the tree of order k with maximum diameter 2; in which case a star of k > 2 has k − 1 leaves.

A star with 3 edges is called a claw.

The star Sk is edge-graceful when k is even and not when k is odd. It is an edge-transitive matchstick graph, and has diameter 2 (when k > 1), girth ∞ (it has no cycles), chromatic index k, and chromatic number 2 (when k > 0). Additionally, the star has large automorphism group, namely, the symmetric group on k letters.

Stars may also be described as the only connected graphs in which at most one vertex has degree greater than one.

Relation to other graph families[edit]

Claws are notable in the definition of claw-free graphs, graphs that do not have any claw as an induced subgraph.[1][2] They are also one of the exceptional cases of the Whitney graph isomorphism theorem: in general, graphs with isomorphic line graphs are themselves isomorphic, with the exception of the claw and the triangle K3.[3]

A star is a special kind of tree. As with any tree, stars may be encoded by a Prüfer sequence; the Prüfer sequence for a star K1,k consists of k − 1 copies of the center vertex.[4]

Several graph invariants are defined in terms of stars. Star arboricity is the minimum number of forests that a graph can be partitioned into such that each tree in each forest is a star,[5] and the star chromatic number of a graph is the minimum number of colors needed to color its vertices in such a way that every two color classes together form a subgraph in which all connected components are stars.[6] The graphs of branchwidth 1 are exactly the graphs in which each connected component is a star.[7]

The star graphs S3, S4, S5 and S6.

Other applications[edit]

The set of distances between the vertices of a claw provides an example of a finite metric space that cannot be embedded isometrically into a Euclidean space of any dimension.[8]

The star network, a computer network modeled after the star graph, is important in distributed computing.

A geometric realization of the star graph, formed by identifying the edges with intervals of some fixed length, is used as a local model of curves in tropical geometry. A tropical curve is defined to be a metric space that is locally isomorphic to a star shaped metric graph.


  1. ^ Faudree, Ralph; Flandrin, Evelyne; Ryjáček, Zdeněk (1997), Claw-free graphs — A survey, Discrete Mathematics 164 (1–3): 87–147, doi:10.1016/S0012-365X(96)00045-3, MR 1432221 .
  2. ^ Chudnovsky, Maria; Seymour, Paul (2005), "The structure of claw-free graphs", Surveys in combinatorics 2005, London Math. Soc. Lecture Note Ser. 327, Cambridge: Cambridge Univ. Press, pp. 153–171, MR 2187738 .
  3. ^ Whitney, Hassler (January 1932), Congruent Graphs and the Connectivity of Graphs, American Journal of Mathematics 54 (1): 150–168, JSTOR 2371086 .
  4. ^ Gottlieb, J.; Julstrom, B. A.; Rothlauf, F.; Raidl, G. R. (2001), "Prüfer numbers: A poor representation of spanning trees for evolutionary search", Proc. Genetic and Evolutionary Computation Conference, Morgan Kaufmann, pp. 343–350 .
  5. ^ Hakimi, S. L.; Mitchem, J.; Schmeichel, E. E. (1996), Star arboricity of graphs, Discrete Math. 149: 93–98, doi:10.1016/0012-365X(94)00313-8 
  6. ^ Fertin, Guillaume; Raspaud, André; Reed, Bruce (2004), Star coloring of graphs, Journal of Graph Theory 47 (3): 163–182, doi:10.1002/jgt.20029 .
  7. ^ Robertson, Neil; Seymour, Paul D. (1991), Graph minors. X. Obstructions to tree-decomposition, Journal of Combinatorial Theory 52 (2): 153–190, doi:10.1016/0095-8956(91)90061-N .
  8. ^ Linial, Nathan (2002), "Finite metric spaces–combinatorics, geometry and algorithms", Proc. International Congress of Mathematicians, Beijing 3, pp. 573–586, arXiv:math/0304466 

Original courtesy of Wikipedia: http://en.wikipedia.org/wiki/Star_(graph_theory) — Please support Wikipedia.
This page uses Creative Commons Licensed content from Wikipedia. A portion of the proceeds from advertising on Digplanet goes to supporting Wikipedia.
24762 videos foundNext > 

Algorithms - Graph Theory - 03 - BFS (Arabic)

Content Link: https://www.dropbox.com/s/wcb20ojwuhb7o4m/Algorithms_Graph_Theory_03_BFS.cpp Content: - What is BFS? Basic Code - Trick for simpler code - Find...

Graph Theory: Sorted Edges Algorithm (Cheapest Link Algorithm)

This lesson explains how to apply the sorted edges algorithm to try to find the lowest cost Hamiltonian circuit. Site: http://mathispower4u.com.

Graph Theory: Nearest Neighbor Algorithm (NNA)

This lesson explains how to apply the nearest neightbor algorithm to try to find the lowest cost Hamiltonian circuit. Site: http://mathispower4u.com.

Graph Theory: 33. Petersen Graph is Not Hamiltonian

An introduction to Graph Theory by Dr. Sarada Herke. Related Videos: http://youtu.be/FgHuQw7kb-o - Graph Theory: 30. The 5 Known Vertex-Transitive Non-Hamiltonian Graphs ...

Ramsey theory on QI (Higher Quality)

A question to do with Ramsey theory, an area of Graph Theory, appears on QI. This is from episode 6 of series 'G' ('Genius'), broadcast 1st Jan 2010.

Introduction to Graph Theory - Part 2

www.Stats-Lab.com | Discrete Maths | Graph Theory.

Graph Traversals :: Depth first search (DFS) & Breadth First Search (BFS) Algorithms.

Graph ADT how-to - performing a: - Breadth-first Traversal - Depth-first Traversal.

Finding paths in graph theory

Video to find all paths between two vertices in a graph.

Wolf Prize Laureate Laszlo Lovasz on "Which Graphs Are Extremal?"

Which graphs are extremal? Extremal graph theory has matured in a sense; besides studying specific extremal problems, now we can pose and, in part, answer ge...

Graphs: Dijkstra's Algorithm

How to find least-cost paths in a graph using Dijkstra's Algorithm. This video is distributed under the Creative Commons Attribution 2.5 Canada License. http...

24762 videos foundNext > 

We're sorry, but there's no news about "Star (graph theory)" right now.


Oops, we seem to be having trouble contacting Twitter

Support Wikipedia

A portion of the proceeds from advertising on Digplanet goes to supporting Wikipedia. Please add your support for Wikipedia!

Searchlight Group

Digplanet also receives support from Searchlight Group. Visit Searchlight