Independence Number

The (upper) vertex independence number of a graph, often called simply "the" independence number, is the cardinality of the largest independent vertex set, i.e., the size of a maximum independent vertex set (which is the same as the size of a largest maximal independent vertex set). The independence number is most commonly denoted , but may also be written  (e.g., Burger et al. 1997) or  (e.g., Bollobás 1981).

The independence number of a graph is equal to the largest exponent in the graph's independence polynomial.

The lower independence number  may be similarly defined as the size of a smallest maximal independent vertex set in  (Burger et al. 1997).

The lower irredundance number , lower domination number , lower independence number , upper independence number , upper domination number , and upper irredundance number  satsify the chain of inequalities

(1)

(Burger et al. 1997).

The ratio of the independence number of a graph  to its vertex count is known as the independence ratio of  (Bollobás 1981).

For a connected regular graph  on  vertices with vertex degree  and smallest graph eigenvalue ,

(2)

(A. E. Brouwer, pers. comm., Dec. 17, 2012).

For  the graph radius,

(3)

(DeLa Vina and Waller 2002). Lovasz (1979, p. 55) showed that when  is the path covering number,

(4)

with equality for only complete graphs (DeLa Vina and Waller 2002).

The matching number  of a graph  is equal to the independence number  of its line graph .

By definition,

(5)

where  is the vertex cover number of  and  its vertex count (West 2000).

Known value for some classes of graph are summarized below.

graph		OEIS	values
alternating group graph		A000000	1, 1, 4, 20, 120, ...
-Andrásfai graph ()		A000027	3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
-antiprism graph ()		A004523	2, 2, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 10, ...
-Apollonian network		A000244	1, 3, 9, 27, 81, 243, 729, 2187, ...
complete bipartite graph		A000027	1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
complete graph	1	A000012	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
complete tripartite graph		A000027	1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
cycle graph  ()		A004526	1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, ...
empty graph		A000027	1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
-folded cube graph ()		A058622	1, 1, 4, 5, 16, 22, 64, 93, 256, ...
grid graph		A000982	1, 2, 5, 8, 13, 18, 25, 32, 41, 50, 61, 72, ...
grid graph		A036486	1, 4, 14, 32, 63, 108, 172, 256, 365, 500, ...
-halved cube graph		A005864	1, 1, 4, 5, 16, 22, 64, 93, 256, ...
-Hanoi graph		A000244	1, 3, 9, 27, 81, 243, 729, 2187, ...
hypercube graph		A000079	1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, ...
-Keller graph	{4 for n=1; 5 for n=2; 2^n otherwise" src="https://mathworld.wolfram.com/images/equations/IndependenceNumber/Inline61.svg" style="height:93px; width:132px" />	A258935	4, 5, 8, 16, 32, 64, 128, 256, 512, ...
-king graph ()		A008794	1, 4, 4, 9, 9, 16, 16, 25, 25
-knight graph ()	{4 for n=2; (1+(-1)^(n+1)+2n^2)/4 otherwise" src="https://mathworld.wolfram.com/images/equations/IndependenceNumber/Inline67.svg" style="height:65px; width:335px" />	A030978	4, 5, 8, 13, 18, 25, 32, 41, 50, 61, 72, ...
Kneser graph
-Mycielski graph	{1 for n=1,2; 3·2^(n-3)-1 otherwise" src="https://mathworld.wolfram.com/images/equations/IndependenceNumber/Inline71.svg" style="height:61px; width:245px" />	A266550	1, 1, 2, 5, 11, 23, 47, 95, 191, 383, 767, ...
Möbius ladder  ()		A109613	3, 3, 5, 5, 7, 7, 9, 9, 11, 11, 13, 13, 15, ...
odd graph	{1 for n=1; (2n-2; n-2) otherwise" src="https://mathworld.wolfram.com/images/equations/IndependenceNumber/Inline76.svg" style="height:85px; width:208px" />	A000000	1, 1, 4, 15, 56, 210, 792, 3003, 11440, ...
-pan graph		A000000	2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, ...
path graph		A004526	1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, ...
prism graph  ()		A052928	2, 4, 4, 6, 6, 8, 8, 10, 10, 12, 12, ...
-Sierpiński carpet graph			4, 32, 256, ...
-Sierpiński gasket graph			1, 3, 6, 15, 42, ...
star graph	{1 for n=1; n-1 otherwise" src="https://mathworld.wolfram.com/images/equations/IndependenceNumber/Inline87.svg" style="height:61px; width:157px" />	A028310	1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
triangular graph  ()		A004526	1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, ...
-web graph ()		A032766	4, 6, 7, 9, 10, 12, 13, 15, 16, 18, 19, 21, ...
wheel graph		A004526	1, 2, 2, 3, 3, 4, 4, 5, 5, ...

Precomputed independence numbers for many named graphs can be obtained in the Wolfram Language using GraphData[graph, "IndependenceNumber"].

---

REFERENCES

Bollobás, B. "The Independence Ratio of Regular Graphs." Proc. Amer. Math. Soc. 83, 433-436, 1981.

Burger, A. P.; Cockayne, E. J.; and Mynhardt, C. M. "Domination and Irredundance in the Queens' Graph." Disc. Math. 163, 47-66, 1997.

Cockayne, E. J. and Mynhardt, C. M. "The Sequence of Upper and Lower Domination, Independence and Irredundance Numbers of a Graph." Disc. Math. 122, 89-102, 1993).

DeLa Vina, E. and Waller, B. "Independence, Radius and Path Coverings in Trees." Congr. Numer. 156, 155-169, 2002.

Lovasz, L. Combinatorial Problems and Exercises. Academiai Kiado, 1979.

Skiena, S. "Maximum Independent Set" §5.6.3 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 218-219, 1990.

Sloane, N. J. A. Sequences A000012/M0003, A000027/M0472, A000079/M1129, A000244/M2807, A000982/M1348, A004523, A004526, A005864/M1111, A008794, A028310, A030978, A032766, A036486, A052928, A058622, A109613, A258935, and A266550West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.

اخر الاخبار

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

في مستشفى الكفيل.. تقنية "إليزاروف" تنقذ شابًّا من معاناة طويلة

رئيس هيأة التربية والتعليم يطّلع على سير العملية التعليمية في جامعة العميد

المشاركون في الملتقى التربوي يطلعون على عدد من مشاريع العتبة العباسية المقدسة

ضمن فعاليات الملتقى التربوي.. قسم العلاقات ينظم ورشة تعريفية عن دور المنسق التربوي

المزيد

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

دراسة تكشف الأفضل للصحة.. البيض البني أم الأبيض؟

أندر الأمراض.. نوم مستمر يحول الحياة إلى "كابوس"

ملعقة من زيت الزيتون يوميا.. ما تأثيرها على صحتك؟

هل يؤثر ذكاء الأطفال على أعمارهم؟.. دراسة حديثة تكشف العلاقة

المزيد

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

علماء: "إنزيم الدهون" يخفي سرا مذهلا منذ 60 عاما

اكتشاف كيميائي على قمر زحل الشهير يغير المفاهيم العلمية

زلزال داخل ميتا.. إلغاء مئات الوظائف بقسم الذكاء الاصطناعي

ناسا تكشف: كوكب الأرض أصبح أقل لمعانا خلال العقود الماضية

المزيد

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

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