کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4648520 1342415 2012 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Signed 2-independence in digraphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Signed 2-independence in digraphs
چکیده انگلیسی

Let DD be a finite and simple digraph with vertex set V(D)V(D), and let f:V(D)→{−1,1}f:V(D)→{−1,1} be a two-valued function. If ∑x∈N−[v]f(x)≤1∑x∈N−[v]f(x)≤1 for each v∈V(D)v∈V(D), where N−[v]N−[v] consists of vv and all vertices of DD from which arcs go into vv, then ff is a signed 2-independence function on DD. The sum f(V(D))f(V(D)) is called the weight w(f)w(f) of ff. The maximum of weights w(f)w(f), taken over all signed 2-independence functions ff on DD, is the signed 2-independence number αs2(D) of DD.In this work, we mainly present upper bounds on αs2(D), as for example αs2(D)≤n−2⌈Δ−/2⌉ and αs2(D)≤Δ++1−2⌈δ−2⌉Δ++1⋅n, where nn is the order, Δ−Δ− and δ−δ− are the maximum and the minimum indegree and Δ+Δ+ is the maximum outdegree of the digraph DD. Some of our theorems imply well-known results on the signed 2-independence number of graphs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 312, Issue 2, 28 January 2012, Pages 465–471
نویسندگان
,