کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
9513406 1632462 2005 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The orientation number of two complete graphs with linkages
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
The orientation number of two complete graphs with linkages
چکیده انگلیسی
For a connected graph G containing no bridges, let D(G) be the family of strong orientations of G; and for any D∈D(G), we denote by d(D) the diameter of D. The orientation number d→(G) of G is defined by d→(G)=min{d(D)|D∈D(G)}. In this paper, we study the orientation numbers of a family of graphs, denoted by G(p,q;m), that are obtained from the disjoint union of two complete graphs Kp and Kq by adding m edges linking them in an arbitrary manner. Define d→(m)=min{d→(G):G∈G(p,q;m)}. We prove that d→(2)=4 and min{m:d→(m)=3}=4. Let α=min{m:d→(m)=2}. We evaluate the exact value of α when p⩽q⩽p+3 and show that 2p+2⩽α⩽2p+4 for q⩾p+4.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 295, Issues 1–3, 28 May 2005, Pages 91-106
نویسندگان
, ,