آمار
| تعداد نشریات | 5 |
| تعداد شماره‌ها | 111 |
| تعداد مقالات | 1,247 |
| تعداد مشاهده مقاله | 1,199,552 |
| تعداد دریافت فایل اصل مقاله | 1,060,264 |
On the 2-independence subdivision number of graphs | ||
| Communications in Combinatorics and Optimization | ||
| مقاله 11، دوره 7، شماره 1، شهریور 2022، صفحه 105-112 اصل مقاله (353.36 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2021.27060.1186 | ||
| نویسندگان | ||
| Nacéra Meddah* 1؛ Mostafa Blidia2؛ Mustapha Chellali3 | ||
| 1Department of Mathematics University of Blida B.P. 270, Blida, Algeria | ||
| 2Department of Mathematics, University of Blida 1. B.P. 270, Blida, Algeria | ||
| 3Department of Mathematics University of Blida 1, B.P. 270, Blida, Algeria | ||
| چکیده | ||
| A subset $S$ of vertices in a graph $G=(V,E)$ is $2$-independent if every vertex of $S$ has at most one neighbor in $S.$ The $2$-independence number is the maximum cardinality of a $2$-independent set of $G.$ In this paper, we initiate the study of the $2$-independence subdivision number $\mathrm{sd}% _{\beta _{2}}(G)$ defined as the minimum number of edges that must be subdivided (each edge in $G$ can be subdivided at most once) in order to increase the $2$-independence number. We first show that for every connected graph $G$ of order at least three, $1\leq \mathrm{sd}_{\beta _{2}}(G)\leq 2,$ and we give a necessary and sufficient condition for graphs $G$ attaining each bound. Moreover, restricted to the class of trees, we provide a constructive characterization of all trees $T$ with $\mathrm{sd}_{\beta _{2}}(T)=2,$ and we show that such a characterization suggests an algorithm that determines whether a tree $T$\ has\textrm{\ }$\mathrm{sd}_{\beta _{2}}(T)=2$\ or $\mathrm{sd}_{\beta _{2}}(T)=1$\ in polynomial time. | ||
| کلیدواژه‌ها | ||
| Trees؛ 2-independence؛ subdivision numbers | ||
| مراجع | ||
|
[1] M. Atapour, S.M. Sheikholeslami, A. Hansberg, L. Volkmann, and A. Khodkar, 2-domination subdivision number of graphs, AKCE Int. J. Graphs. Combin. 5 (2008), no. 2, 165–173.
[2] M. Atapour, S.M. Sheikholeslami, and A. Khodkar, Roman domination subdivision number of graphs, Aequationes Math. 78 (2009), no. 3, 237–245.
[3] M. Chellali, O. Favaron, A. Hansberg, and L. Volkmann, k-domination and kindependence in graphs: A survey, Graphs Combin. 28 (2012), no. 1, 1–55.
[4] M. Chellali, O. Favaron, T.W. Haynes, and D. Raber, Ratios of some domination parameters in trees, Discrete Math. 308 (2008), no. 17, 3879–3887.
[5] J.F. Fink and M.S. Jacobson, On n-domination, n-dependence and forbidden subgraphs, Graph Theory with Applications to Algorithms and Computer Science, John Wiley and Sons. New York, 1985, pp. 301–311.
[6] T.W. Haynes, S.M. Hedetniemi, and S.T. Hedetniemi, Domination and independence subdivision numbers of graphs, Discuss. Math. Graph Theory 20 (2000), no. 2, 271–280.
[7] T.W. Haynes, S.T. Hedetniemi, and L.C. van des Merwe, Total domination subdivision numbers, J. Combin. Math. Combin. Comput. 44 (2003), no. 3, 115–128.
| ||
|
آمار تعداد مشاهده مقاله: 421 تعداد دریافت فایل اصل مقاله: 562 |
||