Upper bounds on the signed edge domination number of a graph
Upper bounds on the signed edge domination number of a graph
复制标题
图的有符号边支配数的上限
DOI：
10.1016/j.disc.2020.112201
复制
发表时间：
2021-02
影响因子：
0.8
通讯作者：
Yan Yang
中科院分区：
文献类型：
--
作者：
Fengming Dong;Jun Ge;Yan Yang
简单图G=（V，E）的符号边控制函数（或SEDF）是一个函数f：E→{1，− 1}使得对于每个边e∈ E，∑ e′∈ N [e] f（e′）≥ 1成立，其中N [e]是G中与e至少有一个端点的边的集合。设γ s′（G）表示f（G）在所有SEDF f中的最小值，其中f（G）=∑ e∈ Ef（e）. 2005年，徐光春证明了γ s′（G）≤ n− 1，其中n是G的阶.这一猜想在v od d（G）= 0和v even（G）= 0两种情况下得到了证明，其中v od d（G）（分别为v e v e n（G））是奇数（分别为even）顶点。本文证明了徐氏猜想对v even（G）∈{1，2}.对任意n阶简单图G，当v e v e n（G）> 0时，γ s′（G）≤ n+ v o d d（G）scin 2且γ s′（G）≤ n− 2+ v e v e n（G），从而γ s′（G）≤（4 n− 2）scin 3.我们的结果改进了γ s '（G）≤ 3 n 2的当前最佳上界。
A signed edge domination function (or SEDF) of a simple graph G=(V, E) is a function f: E→{1,− 1} such that∑ e′∈ N [e] f (e′)≥ 1 holds for each edge e∈ E, where N [e] is the set of edges in G that share at least one endpoint with e. Let γ s′(G) denote the minimum value of f (G) among all SEDFs f, where f (G)=∑ e∈ E f (e). In 2005, Xu conjectured that γ s′(G)≤ n− 1, where n is the order of G. This conjecture has been proved for the two cases v o d d (G)= 0 and v e v e n (G)= 0, where v o d d (G)(resp. v e v e n (G)) is the number of odd (resp. even) vertices in G. This article proves Xu’s conjecture for v e v e n (G)∈{1, 2}. We also show that for any simple graph G of order n, γ s′(G)≤ n+ v o d d (G)∕ 2 and γ s′(G)≤ n− 2+ v e v e n (G) when v e v e n (G)> 0, and thus γ s′(G)≤(4 n− 2)∕ 3. Our result improves the best current upper bound of γ s′(G)≤⌈ 3 n∕ 2⌉.
登录
查看更多内容
DOI：
10.1006/jctb.1999.1905
发表时间：
1999-07
期刊：
J. Comb. Theory B
影响因子：
--
作者：
Z. Füredi;D. Mubayi
通讯作者：
Z. Füredi;D. Mubayi
影响因子：
0.7
作者：
H. Karami;S. M. Sheikholeslami;A. Khodkar
通讯作者：
H. Karami;S. M. Sheikholeslami;A. Khodkar
DOI：
--
发表时间：
2014
期刊：
Australas. J Comb.
影响因子：
--
作者：
S. Akbari;Hossein Esfandiari;E. Barzegary;Saeed Seddighin
通讯作者：
S. Akbari;Hossein Esfandiari;E. Barzegary;Saeed Seddighin
DOI：
10.1016/0012-365x(94)00324-c
发表时间：
1996-10
期刊：
Discret. Math.
影响因子：
--
作者：
B. Zelinka
通讯作者：
B. Zelinka
DOI：
10.1016/j.disc.2006.09.050
发表时间：
2008-05
期刊：
Discret. Math.
影响因子：
--
作者：
Weidong Chen;E. Song
通讯作者：
Weidong Chen;E. Song