Abstract:

G գրաֆի լիակատար ներկումը այդ գրաֆի այն ներկումն է, որի դեպքում հարևան գագաթները և կողերը ներկված են տարբեր գույներով և ցանկացած գագաթ և նրան կից կողերը ևս ներկված են տարբեր գույներով: G գրաֆի լիակատար ներկումը 1 , . . . ,է գույներով կանվանենք միջակայքային լիակատար t-ներկում, եթե բոլոր գույները օգտագործվել են, և յուրաքանչյուր v գագաթին կից կողերը և այդ գագաթը ներկված են dG(v) + 1 հաջորդական գույներով, որտեղ dG(v)-ով նշանակված է v գագաթի աստիճանը G գրաֆում: Այս աշխատանքում ապացուցվում է, որ յուրաքանչյուր կողմում միևնույն քանակի գագաթներ պարունակող լրիվ բազմակողմանի գրաֆներն ունեն միջակայքային լիակատար ներկում: Ավելին, աշխատանքում տրվում են որոշ գնահատականներ այս գրաֆների միջակայքային լիակատար ներկումներում մասնակցող գույների նվազագույն և առավելագույն հնարավոր թվի համար: Աշխատանքում ուսումնասիրվում են նաև Qn հիպերխորանարդների միջակայքային լիակատար ներկումներ: Մասնավորապես, ապացուցվում է, որ Qn (n ≥ 3) հիպերխորանարդն ունի միջակայքային լիակատար t- ներկում այն և միայն այն դեպքում, երբ n + 1 ≤ t ≤ ( (n+1Xn+2)/2):
; Тотальной раскраской графа G назовем такую раскраску вершин и ребер графа G, при которой смежные вершины, смежные ребра и вершины, инцидентные ребрам, окрашены в различные цвета. Интервальной тотальной t— раскраской графа G назовем тотальную раскраску графа G в цвета 1, . . . ,t при которой все цвета использованы, и ребра, инцидентные каждой вершине v вместе с v, окрашены в dG(v) + 1 последовательных цветов, где dG(v) - это степень вершины v в графе G. В настоящей работе доказано, что все полные многодольные графы с одинаковым количеством вершин в каждой доле имеют интервальную тотальную раскраску. Кроме того, получены некоторые оценки наименьшего и наибольшего возможного числа цветов в интервальных тотальных раскрасках этих графов. В работе также исследованы интервальные тотальные раскраски гиперкубов Qn. В частности, доказано, что гиперкуб Qn (n ≥ 3 ) имеет интервальную тотальную раскраску тогда и только тогда, когда n + 1 ≤ t ≤ ( (n+1Xn+2)/2) .

Identifier:

oai:noad.sci.am:135977