吉林大学学报(理学版) ›› 2021, Vol. 59 ›› Issue (3): 525-530.

• • 上一篇    下一篇

似星树与路的乘积图的任意可分性

张盼盼, 刘凤霞, 孟吉翔   

  1. 新疆大学 数学与系统科学学院, 乌鲁木齐 830046
  • 收稿日期:2020-10-07 出版日期:2021-05-26 发布日期:2021-05-23

Arbitrarily Partitionable Product Graph of Star-Like Tree and  Path

ZHANG Panpan, LIU Fengxia, MENG Jixiang   

  1. College of Mathematics and System Science, Xinjiang University, Urumqi 830046, China
  • Received:2020-10-07 Online:2021-05-26 Published:2021-05-23
  • Contact: 刘凤霞 E-mail:xjulfx@163.com

摘要: 设似星树S=S(a1,a2,…,at,b1,b2,…,bs), 其中ai(1≤i≤t)是奇数, bj(1≤j≤s)是偶数. 首先, 讨论似星树S与路Pl的乘积图SPl在t和s不同取值下是否为任意可分图, 并用图不含完美匹配的方法和反证法给出其不是任意可分图的充分条件; 其次, 分析图SPl的Hamilton性, 并用似星树的任意可分性给出图为任意可分图的充分条件. 结果表明, 当t=1且s≤2时, 图SPl是任意可分图; 当t≥2或t=0, 或者t=1, s≥3, b1=b2=…=bs, t+s≥l+2时, 图SPl均不是任意可分图.

关键词: 任意可分图, 乘积图, 似星树, 可迹图

Abstract: Let S=S(a1,a2,…,at,b1,b2,…,bs) be a star-like tree, where ai is odd, bj is even for 1≤i≤t, 1≤j≤s. Firstly, under different values of t and s, we discuss whether the product graph SP of a star-like tree S and a path Pl is arbitrarily partitionable graph. We give some sufficient conditions for S such that SP is not arbitrarily partitionable graph by contradiction and the method of graphs without perfect matching. Secondly, by analyzing the Hamiltonian property of graphs SPl and using arbitrary partition of star-like trees, we give some sufficient conditions for S such that SP is arbitrarily partitionable graph. The results show that if t=1 and s≤2, then SPl is arbitrarily partitionable graph; if t≥2 or t=0, or t=1, s≥3, b1=b2=…=bs, t+s≥l+2, then SPl is not arbitrarily partitionable graph.

Key words: arbitrarily partitionable graph, product graph, star-like tree, traceable graph

中图分类号: 

  • O157.5