digplanet beta 1: Athena
Share digplanet:

Agriculture

Applied sciences

Arts

Belief

Business

Chronology

Culture

Education

Environment

Geography

Health

History

Humanities

Language

Law

Life

Mathematics

Nature

People

Politics

Science

Society

Technology

Star
Star network 7.svg
The star S7. (Some authors index this as S8.)
Vertices k+1
Edges k
Diameter minimum of (2, k)
Girth
Chromatic number minimum of (2, k + 1)
Chromatic index k
Properties Edge-transitive
Tree
Unit distance
Bipartite
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.

References[edit]

  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 (PDF), 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, doi:10.2307/2371086, 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 (PDF), 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.
21615 videos foundNext > 

Graph Theory: 64. Vertex Colouring

In this video we define a (proper) vertex colouring of a graph and the chromatic number of a graph. We discuss some basic facts about the chromatic number as ...

Graph Theory: 57. Planar Graphs

A planar graph is a graph that can be drawn in the plane without any edge crossings. Such a drawing (with no edge crossings) is called a plane graph. A given ...

[Discrete Math 2] Graph Coloring and Chromatic Polynomials

Visit our website: http://bit.ly/1zBPlvm Subscribe on YouTube: http://bit.ly/1vWiRxW Like us on Facebook: http://on.fb.me/1vWwDRc Submit your questions on ...

Lecture - 11 The Graph Theory Approach for Electrical Circuits(Part-I)

Lecture series on Dynamics of Physical System by Prof. Soumitro Banerjee, Department of Electrical Engineering, IIT Kharagpur.For more details on NPTEL visit ...

Graph Theory: Kruskal's Algorithm

This lesson explains how to apply Kruskal's algorithm to find the minimum cost spanning tree. Site: http://mathispower4u.com.

Graph Theory: 48. Complement of a Graph

In this video I define the complement of a graph and what makes a graph self-complementary. I show some examples, for orders 4 and 5 and discuss a ...

Graph Theory: 63. Petersen Graph is Non-Planar

In this video we give two proofs for why the Petersen graph is non-planar. -- Bits of Graph Theory by Dr. Sarada Herke. BIG NEWS - Check out my new course on ...

Basic Graph Theory Example in Hindi

Graph theory in hindi buy ipathshala, learn how to calculate points and edges in a graph.

Graph Theory [ Tree, Co-Tree, Branches, Links...]

A video that clearly explains what different terms in graph theory mean and how to form them. The formation of Tree, Co-Tree, identification of branches, links, ...

Network Theory: 6 Network Topology

For full courses, transcriptions & downloads please see: http://complexitylearning.io We call the overall structure to a network its topology where topology simply ...

21615 videos foundNext > 

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

Loading

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