کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6872326 681740 2014 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Dot product dimensions of graphs
ترجمه فارسی عنوان
ابعاد محصول نقطه ای از نمودارها
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
The concept of dot product dimension of graphs was introduced by Fiduccia et al. (1998), as a relaxation of intersection number. The dot product dimension ρ(G) of a graph G is the minimum k such that there is a function f:V(G)→Rk with the property that two distinct vertices u and v are adjacent if and only if f(u)⋅f(v)≥1, where the dot is the standard inner product in Rk. Fiduccia et al. showed that ρ(G)≤n/2 for any bipartite graph G on n vertices, and ρ(Km,m)=m. They conjectured that ρ(G)≤n/2 for any graph G on n vertices. In this paper, we confirm the conjecture for several classes of graphs, and give several necessary conditions for a graph to be ρ-critical.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 166, 31 March 2014, Pages 159-163
نویسندگان
, ,