树和路字典积图的线性荫度
Linear Arboricity of Lexicographic Products of Trees and Paths
摘要: 近期，李确定了树T
m和路P
n的笛卡尔积图
TmW
Pn、直积图
Tm×Pn、强积图
Tm)Pn的线性荫度，但其证明中漏掉了n=2的情况。本文先对以上三个乘积图的线性荫度补充
n=2的证明，然后计算树和完全图的直积图以及树和路、路和树字典积图的线性荫度。
Abstract:
Li has determined the linear arboricities of Cartesian product graph TmWPn , direct product graph Tm×Pn , and strong product graph Tm)Pn of tree Tm and path Pn recently, but their proofs left out the case n=2 . In this paper, we first supplement the proofs of n=2 to the linear arboricities of the above three product graphs, then we calculate the linear arboricities of the direct product of tree and complete graph, and the lexicographic products of tree and path and path and tree.
参考文献
|
[1]
|
Harary, F. (1970) Covering and Packing in Graphs, I. Annals of the New York Academy of Sciences, 175, 198-205. [Google Scholar] [CrossRef]
|
|
[2]
|
Akiyama, J., Exoo, G. and Harary, F. (1980) Covering and Packing in Graphs III: Cyclic and Acyclic Invariants. Mathematica Slovaca, 30, 405-417.
|
|
[3]
|
Akiyama, J., Exoo, G. and Harary, F. (1981) Covering and Packing in Graphs IV: Linear Arboricity. Networks, 11, 69-72. [Google Scholar] [CrossRef]
|
|
[4]
|
Enomoto, H. and Péroche, B. (1984) The Linear Arboricity of Some Regular Graphs. Journal of Graph Theory, 8, 309-324. [Google Scholar] [CrossRef]
|
|
[5]
|
Guldan, F. (1986) The Linear Arboricity of 10-Regular Graphs. Mathematica Slovaca, 36, 225-228.
|
|
[6]
|
Wu, J.-L. (1999) On the Linear Arboricity of Planar Graphs. Journal of Graph Theory, 31, 129-134. [Google Scholar] [CrossRef]
|
|
[7]
|
Wu, J.-L. and Wu, Y.-W. (2008) The Linear Arboricity of Planar Graphs of Maximum Degree Seven Is Four. Journal of Graph The-ory, 58, 210-220. [Google Scholar] [CrossRef]
|
|
[8]
|
李萍. 树和路乘积图的线性荫度[J]. 应用数学进展, 2022, 11(3): 1242-1246. [Google Scholar] [CrossRef]
|