اخبار و اعلانات

 آمار

تعداد نشریات43
تعداد شماره‌ها1,640
تعداد مقالات13,343
تعداد مشاهده مقاله29,962,187
تعداد دریافت فایل اصل مقاله11,991,544
Derikvand, Tajedin, Oboudi, Mohammad Reza. (1392). On the number of maximum independent sets of graphs. سامانه مدیریت نشریات علمی دانشگاه اصفهان, 3(1), 29-36. doi: 10.22108/toc.2014.4060
Tajedin Derikvand; Mohammad Reza Oboudi. "On the number of maximum independent sets of graphs". سامانه مدیریت نشریات علمی دانشگاه اصفهان, 3, 1, 1392, 29-36. doi: 10.22108/toc.2014.4060
Derikvand, Tajedin, Oboudi, Mohammad Reza. (1392). 'On the number of maximum independent sets of graphs', سامانه مدیریت نشریات علمی دانشگاه اصفهان, 3(1), pp. 29-36. doi: 10.22108/toc.2014.4060
Derikvand, Tajedin, Oboudi, Mohammad Reza. On the number of maximum independent sets of graphs. سامانه مدیریت نشریات علمی دانشگاه اصفهان, 1392; 3(1): 29-36. doi: 10.22108/toc.2014.4060

On the number of maximum independent sets of graphs

Transactions on Combinatorics
مقاله 4، دوره 3، شماره 1، خرداد 2014، صفحه 29-36    اصل مقاله (325.43 K)
نوع مقاله: Research Paper
شناسه دیجیتال (DOI): 10.22108/toc.2014.4060
نویسندگان
Tajedin Derikvand1؛ Mohammad Reza Oboudi* 2
1Islamic Azad University of Marvdasht
2University of Isfahan
چکیده
Let $G$ be a simple graph‎. ‎An independent set is a set of‎ ‎pairwise non-adjacent vertices‎. ‎The number of vertices in a maximum independent set of $G$ is‎ ‎denoted by $\alpha(G)$‎. ‎In this paper‎, ‎we characterize graphs $G$ with $n$ vertices and with maximum‎ ‎number of maximum independent sets provided that $\alpha(G)\leq 2$ or $\alpha(G)\geq n-3$‎.
کلیدواژه‌ها
Independent set؛ Independence number؛ Maximum independent set
مراجع
J. Alexander, J. Cutler and T. Mink (2012) Independent sets in graphs with given minimum degree Electron. J. Combin., Paper 37 19 (3), 11
N. Alon (1991) Independent sets in regular graphs and sum-free subsets of finite groups Israel J. Math. 73, 247-256
D. Cvetkovic and M. Petric (1984) A table of connected graphs on six vertices Discrete Math. 50, 37-49
J. Eckhoff (2004) A new Turan-type theorem for cliques in graphs Discrete Math. 282, 113-122
B. Hedman (1985) The maximum number of cliques in dense graphs Discrete Math. 54, 161-166
G. Hopkins and W. Staton (1985) Graphs with unique maximum independent sets Discrete Math. 57, 245-251
M. J. Jou and G. J. Chang (2000) The number of maximum independent sets in graphs Taiwanese J. Math. 4, 685-695
M. J. Jou and G. J. Chang (1998) Survey on counting maximal independent sets Proceedings of the Second Asian Mathematical Conference 1995 (Nakhon Ratchasima), World Sci. Publ., River Edge, N. J. , 265-275
J. W. Moon and L. Moser (1965) On cliques in graphs Israel J. Math. 3, 23-28
S. Roman (1976) The maximum number of q-cliques in a graph with no $p$-clique Discrete Math. 14, 365-371
P. Turan (1941) Eine Extremalaufgabe aus der Graphentheorie (Hungarian) Mat. Fiz. Lapok 48, 436-452
D. Wood (2007) On the maximum number of cliques in a graph Graphs Combin. 23, 337-352
Y. Zhao (2010) The number of independent sets in a regular graph Combin. Probab. Comput. 19, 315-320
J. Zito (1991) The structure and maximum number of maximum independent sets in trees J. Graph Theory 15, 207-221
آمار
تعداد مشاهده مقاله: 4,559
تعداد دریافت فایل اصل مقاله: 3,133


سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب