1. 喀什大学数学与统计学院
2. 新疆大学数学与系统科学学院
3. 昌吉学院数学与数据科学学院
纸质出版:2024
移动端阅览
[1]西日尼阿依·努尔麦麦提,刘凤霞,蔡华.字典积图的任意可分性[J].新疆大学学报(自然科学版)(中英文),2024,41(02):181-187.
[1]西日尼阿依·努尔麦麦提,刘凤霞,蔡华.字典积图的任意可分性[J].新疆大学学报(自然科学版)(中英文),2024,41(02):181-187. DOI: 10.13568/j.cnki.651094.651316.2023.11.19.0001.
DOI:10.13568/j.cnki.651094.651316.2023.11.19.0001.
给定n个顶点的图G
对于满足■ni=n的任意一个正整数序列(n1
n2
···
nk)
如果都存在顶点集V (G)的划分(V1
V2
···
Vk)
满足Vi导出的子图G[Vi]是连通的
并且|Vi|=ni
其中1≤i≤k
则称图G是任意可分图(简称为AP).两个图G和H的字典积图记为G?H
其顶点集为V (G)×V (H)
(g
h)(g
h)是G?H的一条边当且仅当gg∈E(G)或者g=g且hh∈E(H).讨论了可迹图和任意可分图的字典积图的任意可分性
证明了对于最大度至多为n+1的树T
如果T有一条路P满足全部度数为(T)的顶点属于顶点集V (P)
则字典积图T?Pn是任意可分图;如果G是一个可迹图且H是任意可分图
则图G?H是任意可分图;如果G=S(2
a
b)是一个满足2≤a≤b的任意可分星型树
则图G?G是任意可分图;如果G是哈密顿图且H是一个图
则G?H是任意可分图.
An n-vertex graph G is said to be arbitrarily partitionable(AP
for short)
if for any sequence (n1
n2
···
nk) of positive integers such that ■ ni= n
there exists a partition(V1
V2
···
Vk) of vertex set V(G)such that the subgraph G[Vi] induced by Viis connected and |Vi| = nifor each 1 ≤ i ≤ k. The lexicographic product of two graphs G and H
denoted by G ? H
has vertex set V(G) × V(H) in which(g
h)(g
h) is an edge whenever gg is an edge in G or g = g and hh is an edge in H. In this paper
we mainly discuss the arbitrary partitionability of the lexicographic product of traceable graph and AP graph. We prove that for a tree T of maximum degree at most n+1
if T has a path P such that all the vertices of degree(T) are in V(P)
then the lexicographic product graph T ? Pnis AP; if G is a traceable graph and H is an AP graph
then G ? H is AP; if G = S(2
a
b) is an AP star-like tree with 2 ≤ a ≤ b
then G ? G is AP; if G is Hamiltonian
H is a graph
then G ? H is AP.
ˇCADA R,FLANDRIN E,LI H.Hamiltonicity and pancyclicity of Cartesian products of graphs[J].Discrete Mathematics,2009,309(22):6337-6343.
LIU F X,WU B,MENG J X.Arbitrarily partitionble{2K2,C4}-free graphs[J].Discussiones Mathematicae Graph Theory,2022,42(2):485-500.
MARCZYK A.A note on arbitrarily vertex decomposable graphs[J].Opuscula Mathematica,2006,26(1):109-118.
HORNAK M,WOZNIAK M.On arbitrarily vertex decomposable trees[J].Discrete Mathematics,2008,308(7):1268-1281.
BAUDON O,BENSMAIL J,KALINOWSKI R,et al.On the Cartesian product of an arbitrarily partitionable graph and a traceable graph[J].Discrete Mathematics and Theoretical Computer Science,2014,16(2):225-232.
BARTH D,BAUDON O,PUECH J.Decomposable trees:A polynomial algorithm for tripodes[J].Discrete Applied Mathematics,2002,119(3):205-216.
LIU F X,WU B,MENG J X.Partitioning the Cartesian product of a tree and a cycle[J].Applied Mathematics and Computation,2018,332:90-95.
0
浏览量
74
下载量
0
CSCD
关联资源
相关文章
相关作者
相关机构
京公网安备11010802024621
