Some Notes on Signed Edge Domination in Graphs
Some Notes on Signed Edge Domination in Graphs
复制标题
DOI：
10.1007/s00373-007-0762-8
复制
发表时间：
2008-02
影响因子：
0.7
通讯作者：
H. Karami;S. M. Sheikholeslami;A. Khodkar
中科院分区：
文献类型：
--
作者：
H. Karami;S. M. Sheikholeslami;A. Khodkar
图中某条边的闭邻域ng [e]是由与该边有一个共同端点的所有边组成的集合。设函数onE(G)，即G的边集，入集合{−1,1}。如果对于每个∈E(G)，则称其为G的有符号边支配函数。gis的有符号边支配数γs ' (G)定义为$$\gamma_s^\prime(G) = {\text{min}}\{\sum_{e\in E(G)}f(e)\mid f \,\text{is an SEDF of} G\}$$。最近，Xu证明了γs ' (G)≥|V(G)|−|E(G)|对于所有没有孤立顶点的图G。本文首先刻画了γs ' (G) = |V(G)|−|E(G)|的所有简单连通图。这是b[4]中第4.2题的答案。然后对所有具有精确循环且γs ' (G) = 1−k， 2−k的简单连通图进行分类。
The closed neighborhoodNG[e] of an edgeein a graphGis the set consisting ofeand of all edges having an end-vertex in common withe. Letfbe a function onE(G), the edge set ofG, into the set {−1, 1}. Iffor eache∈E(G), thenfis called a signed edge dominating function ofG. The signed edge domination number γs′(G) ofGis defined as $$\gamma_s^\prime(G) = {\text{min}}\{\sum_{e\in E(G)}f(e)\mid f \,\text{is an SEDF of} G\}$$. Recently, Xu proved that γs′(G) ≥ |V(G)| − |E(G)| for all graphsGwithout isolated vertices. In this paper we first characterize all simple connected graphsGfor which γs′(G) = |V(G)| − |E(G)|. This answers Problem 4.2 of [4]. Then we classify all simple connected graphsGwith preciselykcycles and γs′(G) = 1 −k, 2 −k.