کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6872326 | 681740 | 2014 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Dot product dimensions of graphs
ترجمه فارسی عنوان
ابعاد محصول نقطه ای از نمودارها
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
Journal: Discrete Applied Mathematics - Volume 166, 31 March 2014, Pages 159-163
نویسندگان
Bo-Jr Li, Gerard Jennhwa Chang,