مجله بین المللی ترکیبات
سال:1391 | دوره:1 | شماره:3 |تعداد مقالات:6

فرض کنید G یک زیرگراف فراگیر همبند از Ks,s باشد و فرض کنید K مکمل G نسبت به Ks,s باشد. گراف-k ،G فوق بحرانی نسبت به Ks,s است هرگاه Yt(G)=k و Yt (G+e)=k-2 برای تمام .eÎE(H) مقاله سال 2002 هاینز، هنینگ و وان در مرو با عنوان «گراف های فوق بحرانی احاطه ای تام نسبت به مکمل های نسبی» در مجله Discrerte Mathematics جلد 258، (2002)، صفحات 371-361 قضیه ای (قضیه 11) را برای تولید گراف های (-(2k+2 فوق بحرانی نسبت K2k+1, 2k+1 با قطر 5 به ازای هر2£k  ارایه می کنند. اما خانواده گراف های ارایه شده در اثباتشان آنهایی نیستند که ادعا شده است. در این مقاله تصحیحی از این مقاله را ارایه می کنیم.

فرض کنید G گروهی متناهی با عنصر همانی e باشد. گراف اشتراک زیرگروهیGSI (G)  از G گرافی است که مجموعه رئوس آن V(GSI (G))=G-e و دو راس متمایز x و y در GSI (G) با هم مجاورند اگر و فقط اگر |(x)Ç(y)|>1، جایی که (x) زیر گروه دوره G تولید شده توسط xÎG است. در این مقاله کران پایینی برای عدد استقلال گراف اشتراک زیرگروهی بدست می آوریم. برخی رده های خاص گراف های اشتراک زیرگروهی مربوط به گروه های آبلی متناهی را مشخص می کنیم. نهایتا، گروه هایی که گروه خودریختی های آنها با گروه خودریختی گراف اشتراک زیرگروه آنها یکسان است را مشخص می کنیم.

در این مقاله، مساله پیدا کردن شرطی طبیعی برای اطمینان از اینکه حاصلضرب دکارتی دو گراف، همیلتون-همبند است را مورد بررسی قرار می دهیم. شرابط لازم و کافی ای را برای همیلتون-همبندی Gð‹‹‹‹H وقتی که G گرافی همیلتون-همبند و H درخت است یا G همیلتونی و H گراف K2 است را ارایه می کنیم.

برای یک گراف داده شده G=(V,E)، فرض کنید L(G)={L(v):vÎV} یک فهرست انتساب از پیش توصیف شده باشد. گراف G را L-L(2,1) رنگ پذیر نامیم هرگاه یک برچسب گذاری راسی f از G وجود داشته باشد بطوری که برای هر vÎV داشته باشیم، f(v)ÎL(v)؛ اگر dG (u,v)=1 آنگاه |f(u)-f(v)|³2؛ و اگر dG (u,v)=2 آنگاه .|f(u)-f(v)|³1 اگر گراف G برای هر فهرست انتساب L با شرط L(v)³k برای هر vÎV،L-L(2,1)  رنگ پذیر باشد، در این صورت G، k-L(2,1) انتخاب پذیر گقته می شود. در این مقاله ثابت می کنیم، تمام دورها5-L(2,1)  انتخاب پذیر هستند.

در این مقاله، گراف علامتدار احاطه کننده کمین مشترک از یک گراف علامتدار داده شده را تعریف می کنیم و یک مشخص سازی ساختاری را برای گراف های علامتدار احاطه کننده کمین مشترک ارایه می کنیم. در ادامه، همچنین مشخص سازی های هم ارزی سویچینگ را بدست می آوریم`S ~CMD(S) و CMD(S)~N(S)، جایی کهN(S) و CMD(S) ،`S   به ترتیب گراف علامتدار مکملی، گراف علامتدار کمین مشترک و گراف علامتدار همسایه ای S هستند.

یک گراف دوار نامیده می شود اگر گراف کیلی یک گروه دوری باشد، یعنی ماتریس مجاورت آن دوار باشد. فرض کنید D مجموعه ای از شمارنده های مثبت و محض از عدد صحیح <n1 باشد. گراف دوار صحیح ICGn (D) دارای مجموعه رئوسZn  و مجموعه یال های E(ICGn (G))={{a,b}; gcd (a-b, n)ÎD} است. فرض کنید n=p1 p2...pk m، جایی که p1،...،pk  اعداد اول متمایز هستند و .gcd (p1⋯pk, m)=1 مساله باز مطرح شده در مقاله [A. Ilic, The energy of unitary Cayley graphs, Linear Algebra Appl., 431 (2009) 1881-1889] در خصوص محاسبه انرژی گراف دوار صحیح ICGn (D) برای وقتی که D={p1,p2,…,pk} است به طور کامل حل شده است.