Star Graph

 

The star graph  of order , sometimes simply known as an "-star" (Harary 1994, pp. 17-18; Pemmaraju and Skiena 2003, p. 248; Tutte 2005, p. 23), is a tree on  nodes with one node having vertex degree  and the other  having vertex degree 1. The star graph  is therefore isomorphic to the complete bipartite graph  (Skiena 1990, p. 146).

Note that there are two conventions for the indexing for star graphs, with some authors (e.g., Gallian 2007), adopting the convention that  denotes the star graph on  nodes.

 is isomorphic to "the" claw graph. A star graph is sometimes termed a "claw" (Hoffman 1960) or a "cherry" (Erdős and Rényi 1963; Harary 1994, p. 17).

Star graphs  are always graceful. Star graphs can be constructed in the Wolfram Language using StarGraph[n]. Precomputed properties of star graphs are available via GraphData[{" src="https://mathworld.wolfram.com/images/equations/StarGraph/Inline13.svg" style="height:22px; width:6px" />"Star", n}" src="https://mathworld.wolfram.com/images/equations/StarGraph/Inline14.svg" style="height:22px; width:6px" />].

The chromatic polynomial of  is given by

and the chromatic number is 1 for , and  otherwise.

The line graph of the star graph  is the complete graph .

Note that -stars should not be confused with the "permutation" -star graph (Akers et al. 1987) and their generalizations known as -star graphs (Chiang and Chen 1995) encountered in computer science and information processing.

---

REFERENCES

Akers, S.; Harel, D.; and Krishnamurthy, B. "The Star Graph: An Attractive Alternative to the -Cube." In Proc. International Conference of Parallel Processing, pp. 393-400, 1987.

Chiang, W.-K. and Chen, R.-J. "The -Star Graph: A Generalized Star Graph." Information Proc. Lett. 56, 259-264, 1995.

Erdős, P. and Rényi, A. "Asymmetric Graphs." Acta Math. Acad. Sci. Hungar. 14, 295-315, 1963.

Gallian, J. "Dynamic Survey of Graph Labeling." Elec. J. Combin. DS6. Dec. 21, 2018.

 https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.

Hoffman, A. J. "On the Uniqueness of the Triangular Association Scheme." Ann. Math. Stat. 31, 492-497, 1960.

Pemmaraju, S. and Skiena, S. "Cycles, Stars, and Wheels." §6.2.4 in Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematica. Cambridge, England: Cambridge University Press, pp. 248-249, 2003.

Skiena, S. "Cycles, Stars, and Wheels." §4.2.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 83 and 144-147, 1990.

Tutte, W. T. Graph Theory. Cambridge, England: Cambridge University Press, 2005.

اخر الاخبار

اخبار العتبة العباسية المقدسة

متحف الكفيل يباشر صيانة منسوجات تراثية تابعة للعتبة العسكرية المقدسة

العتبة العباسية المقدسة تستذكر مظلومية الإمام الكاظم (عليه السلام) عبر مجلس عزاء

قسم العلاقات العامة يناقش مع منتدى شباب الإسكان إقامة مهرجان تكريم طالبات المدارس المرتديات العباءة في القادسية

سماحة السيد الصافي يدعو إلى توحيد الجهود في تحقيق التراث لضمان الرصانة والدقة وخدمة الساحة العلمية

المزيد

الآخبار الصحية

6 فواكة تساعدك على الشعور بتحسّن عند المرض

حفاظا على صحة العين.. هذا أفضل وقت لتناول فيتامين أ

الاستخدام اليومي لسماعات الأذن.. أخطر مما تتصور !

هل توقيت نشاطك اليومي يؤثر على صحة دماغك؟.. العلماء يجيبون

المزيد

الآخبار التكنلوجية

ابتكار ألماني قد يغيّر مستقبل صناعة البلاستيك

تحديثات وأرباح عبر المشاهدات.. ما الذي تخطط له "لينكد إن"؟

"الكوكايين الوردي".. مخدر جديد يثير قلق السلطات الأميركية

دراسة: تغيّرات في أسلوب القيادة قد تكشف مبكرا عن الخرف !

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength