Some bounds for the signed edge domination number of a graph
Some bounds for the signed edge domination number of a graph
复制标题
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
S. Akbari;Hossein Esfandiari;E. Barzegary;Saeed Seddighin
中科院分区：
文献类型：
--
作者：
S. Akbari;Hossein Esfandiari;E. Barzegary;Saeed Seddighin
图G中一条边e的闭邻域NG[e]是由e和所有具有公共末端顶点的边组成的集合。设f是图G的边上到集合{−1，1}中的函数。如果E∈NG[x]f(E)≥1对每个x∈E(G)，则f称为G的符号边控制函数。∑x∈E(G)f(X)的最小值取在G的每个符号边控制函数f上，称为G的符号边控制数，记为γ‘S(G)。已证明γ‘S(G)≥n−m∗为通讯作者。S.Akbari et al./AUSTRALAS.J·康宾。58(1)(2014)，60-66 61对每个n阶长m的图G，本文证明了对每个简单图G，γ‘S(G)≥2α’(G)−m 3，其中α‘(G)是G的最大匹配的大小，还证明了对于每个顶点都有奇数度的n阶简单图G，γ’S(G)≤n−2α‘(G)3.
The closed neighbourhood NG[e] of an edge e in a graph G is the set consisting of e and of all edges having a common end vertex with e. Let f be a function on the edges of G into the set {−1, 1}. If e∈NG[x] f(e) ≥ 1 for every x ∈ E(G), then f is called a signed edge domination function of G. The minimum value of ∑ x∈E(G) f(x), taken over every signed edge domination function f of G, is called signed edge domination number of G and denoted by γ′ s(G). It has been proved that γ ′ s(G) ≥ n − m ∗ Corresponding author. S. AKBARI ET AL. /AUSTRALAS. J. COMBIN. 58 (1) (2014), 60–66 61 for every graph G of order n and size m. In this paper we prove that γ′ s(G) ≥ 2α ′(G)−m 3 for every simple graph G, where α′(G) is the size of a maximum matching of G. We also prove that for a simple graph G of order n whose each vertex has an odd degree, γ′ s(G) ≤ n − 2α ′(G) 3 .