Partitions of graphs and multigraphs under degree constraints
Partitions of graphs and multigraphs under degree constraints
复制标题
度约束下图和多重图的划分
DOI：
10.1016/j.dam.2019.10.027
复制
发表时间：
2020-05
影响因子：
1.1
通讯作者：
许宝刚
中科院分区：
文献类型：
--
作者：
宋佳磊;许宝刚
设G是一个可能有多条边但没有环的图，令μ(G)为G的重数（它是一对顶点之间的边数中的最大值），并令s和t为两个非负整数。令 K 4− 为通过移除边从 K 4 获得的图，对于 i∈{1, 2}，令 F i 为通过添加一条连接 C 5 的两个不相邻顶点的长度为 i 的路径从 C 5 获得的简单图。令 F={K 2, 3, K 4−, F 1, F 2}，并令 H 为通过添加一个新顶点并将其连接到两个不同的顶点而从 K 4− 获得的简单图族。 K 4− 的顶点。在本文中，我们证明图 G 允许划分 (S, T)，使得 δ (G [S])≥ s 且 δ (G [T])≥ t if,(1) s≥ 2，t≥ 2，并且 G 是一个简单图，其最小度至少为 s+ t− 1 并且没有 F 的元素作为子图；或者 (2) s≥ 1，t≥ 1，G 的阶数至少为 5，最小阶数至少为 s+ t+ 2 μ(G)− 2，并且 H 中没有元素作为子图。这些改进了一些早期的结果。
Let G be a graph which may have multiple edges but no loops, let μ (G) be the multiplicity of G (which is the maximum among the numbers of edges between a pair of vertices), and let s and t be two nonnegative integers. Let K 4− be the graph obtained from K 4 by removing an edge, for i∈{1, 2}, let F i be the simple graph obtained from C 5 by adding a path of length i joining two nonadjacent vertices of C 5. Let F={K 2, 3, K 4−, F 1, F 2}, and let H be the family of simple graphs obtained from K 4− by adding a new vertex and joining it to two distinct vertices of K 4−. In this paper, we show that a graph G admits a partition (S, T) such that δ (G [S])≥ s and δ (G [T])≥ t if,(1) s≥ 2, t≥ 2, and G is a simple graph with minimum degree at least s+ t− 1 and without elements of F as subgraphs; or (2) s≥ 1, t≥ 1, G has order at least 5, minimum degree at least s+ t+ 2 μ (G)− 2, and no elements of H as subgraphs. These improve a few earlier results.
登录
查看更多内容
DOI：
10.1002/(sici)1097-0118(199611)23:3
发表时间：
1996-11
期刊：
J. Graph Theory
影响因子：
--
作者：
O. Borodin
通讯作者：
O. Borodin
DOI：
10.1016/j.dam.2006.10.005
发表时间：
2007-04
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
C. Bazgan;Z. Tuza;D. Vanderpooten
通讯作者：
C. Bazgan;Z. Tuza;D. Vanderpooten
DOI：
10.1016/j.disc.2018.08.015
发表时间：
2018-12
期刊：
Discret. Math.
影响因子：
--
作者：
Jianfeng Hou;Huawen Ma;Jiguo Yu;Xia Zhang
通讯作者：
Jianfeng Hou;Huawen Ma;Jiguo Yu;Xia Zhang
DOI：
10.1002/(sici)1097-0118(199801)27:1
发表时间：
1998
期刊：
J. Graph Theory
影响因子：
--
作者：
A. Kaneko
通讯作者：
A. Kaneko
DOI：
10.1016/j.dam.2018.10.016
发表时间：
2019-03
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
Thomas Schweser;M. Stiebitz
通讯作者：
Thomas Schweser;M. Stiebitz