پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 41 |
| تعداد شماره‌ها | 1,131 |
| تعداد مقالات | 9,681 |
| تعداد مشاهده مقاله | 17,633,920 |
| تعداد دریافت فایل اصل مقاله | 12,306,984 |
Global Forcing Number for Maximal Matchings under Graph Operations | ||
| Control and Optimization in Applied Mathematics | ||
| دوره 4، شماره 1، مهر 2019، صفحه 53-63 اصل مقاله (774.2 K) | ||
| نوع مقاله: Research Article | ||
| شناسه دیجیتال (DOI): 10.30473/coam.2020.51754.1138 | ||
| نویسنده | ||
| Mostafa Tavakolli* | ||
| Ferdowsi University of Mashhad | ||
| چکیده | ||
| Let $S= \{e_1,\,e_2, \ldots,\,e_m\}$ be an ordered subset of edges of a connected graph $G$. The edge $S$-representation of an edge set $M\subseteq E(G)$ with respect to $S$ is the vector $r_e(M|S) = (d_1,\,d_2,\ldots,\,d_m)$, where $d_i=1$ if $e_i\in M$ and $d_i=0$ otherwise, for each $i\in\{1,\ldots , k\}$. We say $S$ is a global forcing set for maximal matchings of $G$ if $r_e(M_1|S)\neq r_e(M_2|S)$ for any two maximal matchings $M_1$ and $M_2$ of $G$. A global forcing set for maximal matchings of $G$ with minimum cardinality is called a minimum global forcing set for maximal matchings, and its cardinality, denoted by $\varphi_{gm}$, is the global forcing number (GFN for short) for maximal matchings. Similarly, for an ordered subset $F = \{v_1,\,v_2, \ldots,\,v_k\}$ of $V(G)$, the $F$-representation of a vertex set $I\subseteq V(G)$ with respect to $F$ is the vector $r(I|F) = (d_1,\,d_2,\ldots,\,d_k)$, where $d_i=1$ if $v_i\in I$ and $d_i=0$ otherwise, for each $i\in\{1,\ldots , k\}$. We say $F$ is a global forcing set for independent dominatings of $G$ if $r(D_1|F)\neq r(D_2|F)$ for any two maximal independent dominating sets $D_1$ and $D_2$ of $G$. A global forcing set for independent dominatings of $G$ with minimum cardinality is called a minimum global forcing set for independent dominatings, and its cardinality, denoted by $\varphi_{gi}$, is the GFN for independent dominatings. In this paper, we study the GFN for maximal matchings under several types of graph products. Also, we present some upper bounds for this invariant. Moreover, we present some bounds for $\varphi_{gm}$ of some well-known graphs. | ||
| کلیدواژه‌ها | ||
| Global forcing set؛ Global forcing number؛ Maximal matching؛ Maximal independent dominating؛ Product graph | ||
| عنوان مقاله [English] | ||
| عدد فورسینگ عمومی برای تطابق‌های ماکسیمال تحت اعمال گراف | ||
| نویسندگان [English] | ||
| مصطفی توکلی | ||
| دانشگاه فردوسی مشهد | ||
| چکیده [English] | ||
| فرض کنید $S=\{e_1,e_2,\dots,e_m\}$ یک زیرمجموعه مرتب از یال‌های یک گراف همبند $G$ باشد. $S$-نمایش یالی از یک مجموعه یال $M\subseteq E(G)$ نسبت به $S$ بردار $r_e(M|S)=(d_1,d_2,\dots,d_m)$ است که $d_i=1$ اگر $e_i\in M$ و در‌غیر اینصورت $d_i=0$. مجموعه $S$ یک مجموعه فورسینگ عمومی برای تطابق‌های ماکسیمال از $G$ است هرگاه برای هر دو تطابق ماکسیمال $M_1$ و $M_2$ از $G$ داشته باشیم $r_e(M_1|S)=r_e(M_2|S)$. یک مجموعه فورسینگ عمومی برای تطابق‌های ماکسیمال از $G$ با مینیمم اندازه را مجموعه فورسینگ عمومی مینیمم برای تطابق‌های ماکسیمال نامیده می‌شود و تعداد عضوهای آن را با نماد $\varphi_{gm}$ نمایش داده و عدد فورسینگ عمومی (به اختصار \lr{GFN}) برای تطابق‌های ماکسیمال نامیده می‌شود. به‌طور مشابه، برای یک زیرمجموعه مرتب $F=\{v_1,v_2,\dots,v_k\}$ از $V(G)$، $F$-نمایش از یک مجموعه رئوس $I\subseteq V(G)$ نسبت به $F$ بردار $r(I|F)=(d_1,d_2,\dots,d_k)$ است که $d_i=1$ اگر $v_i\in I$ و در‌غیر اینصورت $d_i=0$. مجموعه $F$ یک مجموعه فورسینگ عمومی برای غالب‌های مستقل از $G$ است هرگاه برای هر دو مجموعه غالب مستقل $D_1$ و $D_2$ از $G$ داشته باشیم $r(D_1|F)\neq r(D_2|F)$. یک مجموعه فورسینگ عمومی برای غالب‌های مستقل از $G$ با مینیمم تعداد عضو را مجموعه فورسینگ عمومی مینیمم برای غالب‌های مستقل نامیده شده و تعداد عضوهای که با نماد $\varphi_{gi}$ نشان داده می‌شود \lr{GFN} برای غالب‌های مستقل می‌باشد. در این مقاله \lr{GFN} را برای تطابق‌های ماکسیمال تحت چندین نوع از ضرب‌های گراف مطالعه می‌کنیم. همچنین، کران‌های بالایی برای این متغیر ارائه می‌کنیم. علاوه‌براین، کران‌هایی برای $\varphi_{gm}$ تعدادی از گراف‌های معروف ارائه می‌دهیم. | ||
| کلیدواژه‌ها [English] | ||
| مجموعه فورسینگ سراسری, عدد فورسینگ سراسری, تطابق ماکسیمال, غالب مستقل ماکسیمال, ضرب گراف | ||
| مراجع | ||
|
bibitem{Ada}
Adams P., Mahdian M., Mahmoodian E.S. (2004). ``On the forced matching numbers of bipartite graphs",
Discrete Mathematics, 281, 1--12.
bibitem{Afs}
Afshani P., Hatami H., Mahmoodian E. S. (2004). ``On the spectrum of the forced matching number of graphs",
Australasian Journal of Combinatorics, 30, 147--160.
bibitem{Barr}
Barri'ere L., Dafl'o C., Fiol M. A., Mitjana M. (2009). ``The generalized hierarchical product of graphs",
Discrete Mathematics, 309, 3871--3881.
bibitem{Berg}
Berge C. (1973). ``Graphs and Hypergraphs", North-Holland, Amsterdam.
bibitem{Caro}
Caro Y. (1979). ``New results on the independence number", Technical Report, Tel-Aviv University.
bibitem{Har}
Harary F., Klein D. J., $check{Z}$ivkovi'c T. P. (1991). ``Graphical properties of polyhexes: perfect matching vector and forcing",
Journal of Mathematical Chemistry, 6, 295--306.
bibitem{Henn}
Henning M. A., L"{o}wenstein C., Southey J., Yeo A. (2014).
``A new lower bound on the independence number of a graph and applications", Electronic Journal of Combinatorics, 21,
1--38.
bibitem{Henning}
Henning M. A., Schiermeyer I., Yeo A. (2011).
``A new bound on the domination number of graphs
with minimum degree two", Electronic Journal of Combinatorics, 18, 12.
bibitem{klavzar}
Klav$check{z}$ar S., Tavakoli M. (2020).
``Local metric dimension of graphs: Generalized hierarchical products and some applications",
Applied Mathematics and Computation, 364, 124676.
bibitem{Kle}
Klein D. J., Randi'c M. (1986). ``Innate degree of freedom of a graph", Journal of Computational Chemistry, 8, 516--521.
bibitem{Fajt}
Fajtlowicz S. (1978). ``On the size of independent sets in graphs", Congressus Numerantium,
21, 269--274.
bibitem{Tava}
Tavakoli M., Rahbarnia F., Ashrafi A. R. (2014).
``Applications of the generalized hierarchical product of graphs in computing the vertex and edge
PI indices of chemical graphs", Ricerche di Matematica, 63, 59--65.
bibitem{Dos}
Vuki$check{c}$evi'c D., Zhao S., Sedlar J., Xu S. J., Do$check{s}$li'c T. (2018).
``Global forcing number for maximal matchings'',
Discrete Mathematics, 341, 801--809.
bibitem{Pac}
Pachter L., Kim P. (1998). ``Forcing matchings in square grids", Discrete Mathematics, 190, 287--294.
bibitem{Push}
Pushpalatha A. P., Jothilakshmi G., Suganthi S., Swaminathan V. (2011).
``Forcing independent spectrum in graphs", International Journal of Computer Applications, 21, 1--6.
bibitem{Rid}
Riddle M. E. (2002). ``The minimum forcing number for the torus and hypercube", Discrete Mathematics, 245, 283--292.
bibitem{song}
Song W., Miao L., Wang H., Zhao Y. (2014).
``Maximal matching and edge domination in complete
multipartite graphs", International Journal of Computer Mathematics,
91, 857--862.
bibitem{ids}
Sun L., Wang J. (1999). ``An upper bound for the independent
Domination Number", Journal of Combinatorial Theory. Series B, 76, 240--246.
bibitem{Vuk}
Vuki$check{c}$evi'c D., Kroto H. W., Randi'c M. (2005). ``Atlas of Kekul'{e} valence structures of buckminsterfullerene", Croatica Chemica Acta, 78, 223--234.
bibitem{Vuki}
Vuki$check{c}$evi'c D., Randi'c M. (2005). ``On Kekul'e structures of buckminsterfullerene", Chemical Physics Letters, 401, 446--450.
bibitem{Wei}
Wei V. (1981). ``A lower bound on the stability number of a simple graph",
Bell Laboratories Technical Memorandum 81-11217-9, Murray Hill, NJ.
bibitem{Zha}
Zhang F. J., Li X. L. (1995). ``Hexagonal systems with forcing edges", Discrete Mathematics, 140, 253--263. | ||
|
آمار تعداد مشاهده مقاله: 293 تعداد دریافت فایل اصل مقاله: 211 |
||