极大外平面图的K1,2-孤立数

兰州理工大学学报 ›› 2025, Vol. 51 ›› Issue (4): 152-156.

极大外平面图的K_1,2-孤立数

高巧灵, 安新慧^*

新疆大学数学与系统科学学院, 新疆乌鲁木齐 830046

收稿日期:2023-06-05 出版日期:2025-08-28 发布日期:2025-09-05
通讯作者: 安新慧(1978-),女,甘肃陇西人,博士,副教授.Email:xjaxh@163.com
基金资助:
新疆维吾尔自治区重点实验室开放课题(2022D04026)

K_1,2-isolation number of maximal outerplanar graphs

GAO Qiao-ling, AN Xin-hui

School of Mathematics and System Science, Xinjiang University, Urumqi 830046, China

Received:2023-06-05 Online:2025-08-28 Published:2025-09-05

摘要/Abstract

摘要： 对于顶点子集S⊆V(G),如果R(S)=V\N[S]的导出子图只包含孤立点和孤立边,称S是图G的一个K_1,2-孤立集,图G的K_1,2-孤立数ι₁(G)是G的K_1,2-孤立集的最小基数.基于坏点个数k与2度顶点个数之间的关系,对n+k利用数学归纳法证明极大外平面图的K_1,2-孤立数为$\iota_{1}(G) \leqslant \frac{n+k}{6}$,从而进一步改进了极大外平面图的K_1,2-孤立数的上界,其中k是两个连续2度顶点对在哈密顿圈上的距离至少是3的个数.

关键词: 极大外平面图, K_1,2-孤立集, 坏点

Abstract: A subset S⊆V(G) is a K_1,2-isolating set, if R(S)=V\N[S] have isolated vertices and isolated edges only. The isolation number ι₁(G) of G is the minimum cardinality of a isolation set of G. Based on the relationship between the number of bad vertices k and the number of vertices of degree 2, using mathematical induction on n+k, $\iota_{1}(G) \leqslant \frac{n+k}{6}$ is proved for the maximal outerplanar graph G, and the upper bound of K_1,2-isolating number is further improved,where k is the number of pairs of consecutive vertices of degree 2 with distance at least 3 on the Hamiltonian cycle.

Key words: maximal outerplanar graph, K_1,2-isolating set, bad vertices

中图分类号:

O157.5

高巧灵, 安新慧. 极大外平面图的K_1,2-孤立数[J]. 兰州理工大学学报, 2025, 51(4): 152-156.

GAO Qiao-ling, AN Xin-hui. K_1,2-isolation number of maximal outerplanar graphs[J]. Journal of Lanzhou University of Technology, 2025, 51(4): 152-156.

参考文献

[1] CARO Y,HANSBERG A.Partial domination-the isolation number of a graph[J].Filomat,2017,31(12):3925-3944.
[2] CAMPOS C N,WAKABAYASHI Y.On dominating sets of maximal outerplanar graphs[J].Discrete Applied Mathematics,2013,161(3):330-335.
[3] TOKUNAGA S,JIARASUKSAKUN T,KAEMAWICHANURAT P.Isolation number of maximal outerplanar graphs[J].Discrete Applied Mathematics,2019,267:215-218.
[4] BORG P,KAEMAWICHANURAT P.Partial domination of maximal outerplanar graphs[J].Discrete Applied Mathematics,2020,283:306-314.
[5] LI Z,ZHU E,SHAO Z,et al.On dominating sets of maximal outerplanar and planar graphs[J].Discrete Applied Mathematics,2016,198:164-169.
[6] PLUMMER M D,YE D,ZHA X.Dominating maximal outerplane graphs and Hamiltonian plane triangulations[J].Discrete Applied Mathematics,2020,282:162-167.
[7] LIU C.A note on domination number in maximal outerplanar graphs[J].Discrete Applied Mathematics,2021,293:90-94.
[8] BRAUSE C,HENNING M A.Independent domination in bipartite cubic graphs[J].Graphs and Combinatorics,2019,35:881-912.
[9] CHELLALI M,FAVARON O,HANSBERG A,et al.k-domination and k-independence in graphs:a survey[J].Graphs and Combinatorics,2012,28(1):1-55.
[10] DESORMEAUX W J,HAYNES T W,HENNING M A.Paired domination in graphs[J].Topics in Domination in Graphs,2020,64:31-77.
[11] GODDARD W,HENNING M A.Independent domination in graphs:a survey and recent results[J].Discrete Mathematics,2013,313(7):839-854.
[12] ARUMUGAM S,VELAMMAL S.Connected edge domination in graphs[J].Bulletin of Allahabad Mathematical Society,2009,24(1):43-49.
[13] HENNING M A,KANG L,SHAN E,et al.On matching and total domination in graphs[J].Discrete Mathematics,2008,308(11):2313-2318.
[14] HENNING M A.A survey of selected recent results on total domination in graphs[J].Discrete Mathematics,2009,309(1):32-63.
[15] O’ROURKE J.Galleries need fewer mobile guards:a variation on Chvátal’s theorem[J].Geometriae Dedicata,1983,14:273-283.