ÓÄÊ 519.17
Ì.Ô. ÑÅÌÅÍÞÒÀ
ÏÐÎ ( , )a d -ÄÈÑÒÀÍÖ²ÉÍÓ ÀÍÒÈÌÀò×ÍÓ ÒÀ 1-ÂÅÐØÈÍÍÓ
Á²ÌÀò×ÍÓ ÂÅÐØÈÍÍÓ ÐÎÇ̲ÒÊÈ ÎÊÐÅÌÈÕ ÒÈϲ ÃÐÀÔ²Â
Àíîòàö³ÿ. Óçàãàëüíåíî ðåçóëüòàòè äëÿ êîðîíè P Pn  1, ÿê³ äàþòü çìîãó
ñòâåðäæóâàòè, ùî P Pn  1 íå º ( , )a d -äèñòàíö³éíèì àíòèìàã³÷íèì ãðàôîì äëÿ
äîâ³ëüíèõ çíà÷åíü a ³ d . Îäåðæàíî óìîâó ³ñíóâàííÿ ( , )a d -äèñòàíö³éíî¿ àí-
òèìàã³÷íî¿ ðîçì³òêè ã³ïåðêóáà Qn . Çíàéäåíî ôóíêö³îíàëüí³ çàëåæíîñò³, ùî
ïîðîäæóþòü öåé òèï ðîçì³òêè äëÿ Qn . Ìåòîäîì ìàòåìàòè÷íî¿ ³íäóêö³¿ äî-
âåäåíî, ùî Qn º ( – , )2 1 2
n n n  -äèñòàíö³éíèì àíòèìàã³÷íèì ãðàôîì. Âèç-
íà÷åíî òðè òèïè ãðàô³â, ÿê³ íå äîïóñêàþòü 1-âåðøèííî¿ á³ìàã³÷íî¿ âåð-
øèííî¿ ðîçì³òêè. Âñòàíîâëåíî çâ’ÿçîê äèñòàíö³éíî¿ ìàã³÷íî¿ ðîçì³òêè ðåãó-
ëÿðíîãî ãðàôà G ç 1-âåðøèííîþ á³ìàã³÷íîþ âåðøèííîþ ðîçì³òêîþ G G .
Êëþ÷îâ³ ñëîâà: äèñòàíö³éíà ìàã³÷íà ðîçì³òêà, ( , )a d -äèñòàíö³éíà
àíòèìàã³÷íà ðîçì³òêà, 1-âåðøèííà á³ìàã³÷íà âåðøèííà ðîçì³òêà, n-âèì³ðíèé
êóá, êîðîíà.
ÂÑÒÓÏ
Îñòàíí³ì ÷àñîì ðîçì³òêè ãðàô³â âñå ÷àñò³øå ñòàþòü îá’ºêòîì ³íòåíñèâíèõ
äîñë³äæåíü [1]. Ñòèìóëîì äî ðîçâèòêó öüîãî íàïðÿìêó ³ íàêîïè÷åííÿ òåîðåòè÷-
íèõ äîñÿãíåíü º íàÿâí³ñòü ïðîáëåì ïðàêòè÷íîãî õàðàêòåðó â ð³çíèõ ñôåðàõ
ä³ÿëüíîñò³ [2–7]. ϳä ðîçì³òêîþ ãðàôà G V E ( , ) ðîçóì³þòü â³äîáðàæåííÿ, ùî çà
ïåâíèì ïðàâèëîì ñòàâèòü ó â³äïîâ³äí³ñòü åëåìåíòàì ãðàôà ÷èñëà, ÿê³ íàëåæàòü
çàäàí³é ìíîæèí³. Ðîçì³òêó ââàæàþòü âåðøèííîþ, ðåáåðíîþ àáî òîòàëüíîþ çà-
ëåæíî â³ä îáëàñò³ ¿¿ âèçíà÷åííÿ. Ñïîñ³á îá÷èñëåííÿ âàãè âåðøèíè àáî ðåáðà çà-
ëåæèòü â³ä òèïó ðîçì³òêè. ßêùî âñ³ âàãè ð³âí³ ì³æ ñîáîþ, îäåðæóþòü ìàã³÷íèé
òèï ðîçì³òêè, à ÿêùî âñ³ âàãè ð³çí³ — àíòèìàã³÷íèé. ßêùî âàãè âåðøèí óòâî-
ðþþòü àðèôìåòè÷íó ïðîãðåñ³þ ç ïåðøèì ÷ëåíîì a ³ ð³çíèöåþ d , òî ìàºìî âåð-
øèííó ( , )a d -äèñòàíö³éíó àíòèìàã³÷íó ðîçì³òêó. Âïåðøå âîíà áóëà çàïðîïîíî-
âàíà ó 2012 ðîö³ Ñ. Àðóìóãàìîì ³ Í. Êàìà÷³ [8].
Ó ö³é ñòàòò³ ïðîäîâæèìî äîñë³äæåííÿ, îïèñàí³ â [7–11].  [8] ïîäàíî ïåðø³
çàãàëüí³ ðåçóëüòàòè ³ ñôîðìóëüîâàíî â³äêðèò³ ïðîáëåìè, ÷àñòêîâèé ðîçâ’ÿçîê
ÿêèõ ïðåäñòàâëåíî â [7–12]. Îïèñ õàðàêòåðèñòèê ( , )a d -äèñòàíö³éíèõ àíòèìàã³÷-
íèõ ðåãóëÿðíèõ ãðàô³â, ëàíöþã³â òà êîíñòðóêö³é ãðàô³â, îäåðæàíèõ çà äîïîìî-
ãîþ îäíîì³ñíèõ òà äâîì³ñíèõ îïåðàö³é íàä çàäàíèìè ãðàôàìè, ðîçïî÷àòî ó [7, 8].
Ñ. Àðóìóãàì ³ Í. Êàìà÷³ ïîáóäóâàëè ( , )n2 1 -äèñòàíö³éíó àíòèìàã³÷íó ðîçì³òêó
äåêàðòîâîãî äîáóòêó öèêëó Cn ³ ãðàôà K2 [8], à Ä. Ôðîí÷åê äîâ³â, ùî äèç’þí-
êòèâíå îá’ºäíàííÿ êîï³é äåêàðòîâîãî äîáóòêó äâîõ ïîâíèõ ãðàô³â òà ¿õíüîãî äî-
ïîâíåííÿ º ( , )a 2 -äèñòàíö³éíèì àíòèìàã³÷íèì ³ ( ,a 1)-äèñòàíö³éíèì àíòèìàã³÷íèì
ãðàôàìè â³äïîâ³äíî [7]. Ä. Ôðîí÷åê òàêîæ ïîêàçàâ, ùî äèç’þíêòèâí³ êîﳿ ã³ïåðêó-
áà Q3 óòâîðþþòü ( , )a 1 -äèñòàíö³éíèé àíòèìàã³÷íèé ãðàô.  [10, 11] çíàéäåíî óìîâè
³ñíóâàííÿ ( , )a d -äèñòàíö³éíî¿ àíòèìàã³÷íî¿ ðîçì³òêè öèðêóëÿíòíèõ ãðàô³â, ãðàôà
äðóæáè, ñôîðìóëüîâàíî ³ äîâåäåíî òåîðåìè, ùî ðîçøèðþþòü ñ³ì’¿ íå ( , )a d -äèñ-
òàíö³éíèõ àíòèìàã³÷íèõ ãðàô³â. Ó ðîçä. 2 ö³º¿ ñòàòò³ çàïðîïîíîâàíî ðîçâ’ÿçàííÿ çà-
äà÷ ³ñíóâàííÿ ( , )a d -äèñòàíö³éíî¿ àíòèìàã³÷íî¿ ðîçì³òêè äëÿ êîðîíè P Pn  1 òà
n-âèì³ðíîãî êóáà (ã³ïåðêóáà) Qn .
²íøèé âèä ðîçì³òêè, ùî ðîçãëÿäàºòüñÿ ó ðîçä. 3 — öå 1-âåðøèííà á³ìàã³÷íà
âåðøèííà ðîçì³òêà. Âîíà, ÿê ³ ( , )a d -äèñòàíö³éíà àíòèìàã³÷íà, º ñó÷àñíîþ
134 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 2
© Ì.Ô. Ñåìåíþòà, 2018
ðîçì³òêîþ ³ áóëà ââåäåíà ó 2014 ðîö³ â ñòàòò³ [12], äå âèçíà÷åíî íåîáõ³äíó óìîâó
¿¿ ³ñíóâàííÿ òà îäåðæàíî ðåçóëüòàòè ùîäî òàêèõ òèï³â ãðàô³â, ÿê ëàíöþã Pn , öèêë
Cn , ïîâíèé äâî÷àñòêîâèé ãðàô Km n, , ãðàô G Pn
0 ( ), ïîâíèé ñèìåòðè÷íèé ìóëüòè-
÷àñòêîâèé ãðàô.
Ó ö³é ñòàòò³ áóäåìî äîñë³äæóâàòè òðè òèïè ãðàô³â, ÿê³ íå äîïóñêàþòü 1-âåð-
øèííî¿ á³ìàã³÷íî¿ âåðøèííî¿ ðîçì³òêè. ßê ç’ÿñóâàëîñÿ, äî ¿õíüîãî ÷èñëà
íàëåæàòü ãðàôè ç êîìïîíåíòîþ, ÿêà º ³çîìîðôíîþ ã³ïåðêóáó Q3 . Êð³ì öüîãî, âè-
ÿâëåíî çâ’ÿçîê äèñòàíö³éíî¿ ìàã³÷íî¿ ðîçì³òêè ðåãóëÿðíîãî ãðàôà G ç 1-âåðøèí-
íîþ á³ìàã³÷íîþ âåðøèííîþ ðîçì³òêîþ G G .
1. ÁÀÇβ ÒÅÎÐÅÒÈ×Ͳ ÏÎËÎÆÅÍÍß
Íåõàé G V E ( , ) — ñê³í÷åííèé íåîð³ºíòîâàíèé ãðàô áåç êðàòíèõ ðåáåð òà ïå-
òåëü. Ïîçíà÷èìî f âåðøèííó ðîçì³òêó ãðàôà G , à N u( ) — ìíîæèíó ñóì³æ-
íîñò³ âåðøèíè u V G ( ). Âàãó w u( ) âåðøèíè u äëÿ ðîçì³òêè f âèçíà÷èìî ÿê
ñóìó ì³òîê âåðøèí, ñóì³æíèõ ç u, òîáòî w u f
N u
( ) ( )
( )




 , äå êîæíà âåðøèíà
V G( ).
Ïîíÿòòÿ ( , )a d -äèñòàíö³éíî¿ àíòèìàã³÷íî¿ ³ 1-âåðøèííî¿ á³ìàã³÷íî¿ âåðøèí-
íî¿ ðîçì³òîê ïîâ’ÿçàí³ ç äèñòàíö³éíîþ ìàã³÷íîþ ðîçì³òêîþ, â³äîìîþ òàêîæ ï³ä
íàçâàìè «ñèãìà-ðîçì³òêà» ³ «1-âåðøèííà ìàã³÷íà âåðøèííà ðîçì³òêà». Íàéá³ëüø
ïîïóëÿðíèì ³ ïîøèðåíèì âèÿâèâñÿ òåðì³í «äèñòàíö³éíà ìàã³÷íà ðîçì³òêà», ÿêèé
âèêîðèñòîâóºòüñÿ ³ â ö³é ñòàòò³.
Îçíà÷åííÿ 1 [7]. Äèñòàíö³éíîþ ìàã³÷íîþ ðîçì³òêîþ (àáî 1-âåðøèííîþ
ìàã³÷íîþ âåðøèííîþ ðîçì³òêîþ, àáî ñèãìà-ðîçì³òêîþ) ãðàôà G V E ( , ) ïîðÿäêó
n íàçèâàºòüñÿ ᳺêö³ÿ f V G n: ( ) , , , { }1 2  , äëÿ ÿêî¿ ³ñíóº òàêå íàòóðàëüíå ÷èñëî
k — ìàã³÷íà ñòàëà, ùî äëÿ êîæíî¿ âåðøèíè u V G ( ) âèêîíóºòüñÿ ð³âí³ñòü





N u
f k
( )
( ) . Ãðàô G, ùî äîïóñêຠòàêó ðîçì³òêó, íàçèâàþòü äèñòàíö³éíèì
ìàã³÷íèì ãðàôîì.
Íàâåäåìî îçíà÷åííÿ ( , )a d -äèñòàíö³éíî¿ àíòèìàã³÷íî¿ ðîçì³òêè, çàïðîïîíî-
âàíå Ñ. Àðóìóãàìîì ³ Í. Êàìà÷³, ÿêå áóäåìî çàñòîñîâóâàòè äàë³.
Îçíà÷åííÿ 2 [8]. ( , )a d -äèñòàíö³éíîþ àíòèìàã³÷íîþ ðîçì³òêîþ ãðàôà
G V E ( , ) ïîðÿäêó n íàçèâàºòüñÿ òàêà ᳺêö³ÿ f V G n: ( ) , , , { }1 2  , äëÿ ÿêî¿
ìíîæèíà âñ³õ âàã âåðøèí óòâîðþº àðèôìåòè÷íó ïðîãðåñ³þ a a d a d, , , 2 
 , ( )a n d 1 ç ïåðøèì ÷ëåíîì a ³ ð³çíèöåþ d , äå a d, — ô³êñîâàí³ íåâ³ä’ºìí³
ö³ë³ ÷èñëà, a d	 	1 0, . Ãðàô G , ùî äîïóñêຠòàêó ðîçì³òêó, íàçèâàþòü ( , )a d -äèñ-
òàíö³éíèì àíòèìàã³÷íèì ãðàôîì.
Êîëè d  0, ðîçì³òêà f º äèñòàíö³éíîþ ìàã³÷íîþ, à êîëè d 1 — äèñòàíö³é-
íîþ àíòèìàã³÷íîþ.
Òîòîæíå ïîíÿòòÿ ââ³â Ä. Ôðîí÷åê ó 2013 ðîö³ äëÿ ðîçâ’ÿçàííÿ çàäà÷ îïòè-
ìàëüíîãî ïëàíóâàííÿ òóðí³ð³â ð³çíèõ òèï³â [7]. ³í çàïðîïîíóâàâ íàçèâàòè
ðîçì³òêó f ãðàôà G V E ( , ) ïîðÿäêó n äèñòàíö³éíîþ d-àíòèìàã³÷íîþ, ÿêùî
f V G n: ( ) , , , { }1 2  — ᳺêö³ÿ, çà ÿêî¿ ³ñíóº òàêå âïîðÿäêóâàííÿ âåðøèí G , ùî
¿õí³ âàãè w u w u w un( ), ( ), , ( )1 2  óòâîðþþòü àðèôìåòè÷íó ïðîãðåñ³þ ç ð³çíèöåþ
d , äå u u u V Gn1 2, , , ( )  . Êð³ì òîãî, â [7] ââåäåíî âïîðÿäêîâàíó d -àíòèìàã³÷íó
ðîçì³òêó, ÿêó â òåðì³íàõ ðîáîòè [8] ìîæíà âèçíà÷èòè òàêèì ÷èíîì.
Îçíà÷åííÿ 3. Âïîðÿäêîâàíîþ ( , )a d -äèñòàíö³éíîþ àíòèìàã³÷íîþ ðîçì³òêîþ
ãðàôà G V E ( , ) ïîðÿäêó n íàçèâàºòüñÿ òàêà ᳺêö³ÿ f V G n
 : ( ) , , ,{ }1 2  , äëÿ ÿêî¿
f u ii


( ) , ³ ïîñë³äîâí³ñòü âàã w u w u w un( ), ( ), , ( )1 2  âñ³õ âåðøèí óòâîðþº çðîñòàþ-
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 2 135
÷ó àðèôìåòè÷íó ïðîãðåñ³þ w u a( ) ,1  w u a d w u a n dn( ) , , ( ) ( )2 1     ç ïåð-
øèì ÷ëåíîì a òà ð³çíèöåþ d , äå a d, — íåâ³ä’ºìí³ ö³ë³ ÷èñëà, a d	 	1 0, . Ãðàô G, ùî
äîïóñêຠòàêó ðîçì³òêó f 
 , íàçèâàþòü âïîðÿäêîâàíèì ( , )a d -äèñòàíö³éíèì àíòè-
ìàã³÷íèì ãðàôîì.
Íà ñïîñ³á ïðèñâîºííÿ ì³òîê âåðøèíàì â îçíà÷åíí³ 3 íàêëàäàºòüñÿ äîäàòêîâà
óìîâà, â ðåçóëüòàò³ âåðøèíà ç ìåíøîþ ì³òêîþ ìຠìåíøó âàãó.
Âèçíà÷èìî êëàñè ãðàô³â, âèêîðèñòàí³ â íàñòóïíèõ ðîçä³ëàõ, à ñàìå, n-âè-
ì³ðíèé êóá ³ êîðîíà. Çàçíà÷èìî, ùî n-âèì³ðíèé êóá Qn øèðîêî çàñòîñîâóºòüñÿ
â ìóëüòèêîìï’þòåðíèõ ñèñòåìàõ. Ùå ó 1954 ðîö³ Ó. Êàóòö ìîäåëþâàâ n-öèôðî-
âèé á³íàðíèé êîä ó âèãëÿä³ n-âèì³ðíîãî êóáà äëÿ äîñë³äæåííÿ ïèòàííÿ
«ì³í³ì³çàö³¿ áåçëàäó» ó ñòâîðåíí³ êîä³â äëÿ öèôðîâèõ êîìï’þòåð³â. Çàâäÿêè
ñâî¿ì âëàñòèâîñòÿì Qn º îäí³ºþ ç ïåðñïåêòèâíèõ àðõ³òåêòóð äëÿ ïîáóäîâè ñàìî-
îðãàí³çîâàíîãî ïðîãðàìíîãî çàáåçïå÷åííÿ.
Çã³äíî ç Ô. Õàðàð³ n-âèì³ðíèé êóá Qn âèçíà÷àºòüñÿ ðåêóðñèâíî çà äîïîìî-
ãîþ äåêàðòîâîãî äîáóòêó ãðàô³â: Q K1 2 ³ Q K Qn n  2 1. Òàêèé ãðàô ìຠ2
n
âåðøèí ³ n n2 1 ðåáåð. Êîæíó âåðøèíó Qn ìîæíà çàäàòè n-êîìïîíåíòíèì á³íàð-
íèì âåêòîðîì. Òîìó ï³ä n-âèì³ðíèì (áóëåâèì) êóáîì Qn áóäåìî ðîçóì³òè ãðàô, ó
ÿêîãî ìíîæèíà âåðøèí º ìíîæèíîþ âñ³õ n-êîìïîíåíòíèõ á³íàðíèõ âåêòîð³â, ïðè
öüîìó äâà òàê³ âåêòîðè ââàæàþòüñÿ ñóì³æíèìè òîä³ ³ ò³ëüêè òîä³, êîëè âîíè
â³äð³çíÿþòüñÿ ëèøå îäí³ºþ êîìïîíåíòîþ.
Äèç’þíêòèâíèì îá’ºäíàííÿì ãðàô³â Gi , êîæíèé ç ÿêèõ º êîﳺþ çâ’ÿçíîãî
ãðàôà G, º ãðàô mG G
i
m
i
1

ç m êîìïîíåíòàìè, êîæíà ç ÿêèõ º ³çîìîðôíîþ G .
Ãðàô G H íàçèâàºòüñÿ êîðîíîþ, ÿêùî éîãî îäåðæóþòü ç äèç’þíêòèâíîãî
îá’ºäíàííÿ ãðàôà G ³ n (äå n V G | ( ) |) êîï³é ãðàôà H çà äîïîìîãîþ ç’ºäíàííÿ ³-¿
âåðøèíè G ç êîæíîþ âåðøèíîþ i-¿ êîﳿ H äëÿ i n1 2, , , .
Côîðìóëþºìî íåîáõ³äíó óìîâó ³ñíóâàííÿ ( , )a d -äèñòàíö³éíî¿ àíòèìàã³÷íî¿
ðîçì³òêè ãðàôà G, äå  ³  — ì³í³ìàëüíèé ³ ìàêñèìàëüíèé ñòåïåí³ G â³äïîâ³äíî.
Ëåìà 1 [8]. ßêùî G º ( , )a d -äèñòàíö³éíèì àíòèìàã³÷íèì ãðàôîì ïîðÿäêó n, òî
d
n
n

   

2 1 1
2 1
  ( ) ( )
( )
 
. (1)
Íàñë³äîê 1 [8]. ßêùî ãðàô G º r-ðåãóëÿðíèì ( , )a d -äèñòàíö³éíèì àíòè-
ìàã³÷íèì ïîðÿäêó n ç r 	 2, òî d r .
Íàñòóïíèé íàñë³äîê ñòîñóºòüñÿ óìîâè ³ñíóâàííÿ ( , )a d -äèñòàíö³éíî¿ àíòè-
ìàã³÷íî¿ ðîçì³òêè n-âèì³ðíîãî êóáà Qn .
Íàñë³äîê 2. ßêùî ãðàô Qn º ( , )a d -äèñòàíö³éíèì àíòèìàã³÷íèì, òî n 	 3,
a n , d n .
Äîâåäåííÿ. ßêùî n  2, òî ãðàô Q2 º öèêëîì C4 . ³äîìî, ùî C4 íå äîïóñêàº
( , )a d -äèñòàíö³éíî¿ àíòèìàã³÷íî¿ ðîçì³òêè. Íåõàé n 	 3. Ãðàô Qn º n-ðåãóëÿðíèì,
òîìó
a a d a d a d nn n           ( ) ( ) ( ( ) ) ( )2 2 1 1 2 2  . (2)
гâíÿííÿ (2) çâîäèòüñÿ äî âèäó a d
nn n



2 1
2
2 1
2
( )
. Ç íàñë³äêó 1 ìàºìî
d n , òîìó a n
nn n



2 1
2
2 1
2
( )
àáî a n .
Íàñë³äîê äîâåäåíî.
136 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 2
Àâòîðè ñòàòò³ [12] ââåëè íîâ³ òðè âèäè á³ìàãí³÷íèõ ðîçì³òîê, ñåðåä ÿêèõ
³ 1-âåðøèííà á³ìàã³÷íà âåðøèííà ðîçì³òêà.
Îçíà÷åííÿ 4 [12]. Á³ºêòèâíà ðîçì³òêà f V G n: ( ) , , , { }1 2  ãðàôà
G V E ( , ) ïîðÿäêó n íàçèâàºòüñÿ 1-âåðøèííîþ á³ìàã³÷íîþ âåðøèííîþ, ÿêùî äëÿ
êîæíî¿ âåðøèíè u V G ( ) âèêîíóºòüñÿ





N u
f k
( )
( ) 1 àáî f k
N u
( )
( )



 2 , äå
k k1 2, — ð³çí³ ñòàë³. Ãðàô G, ùî äîïóñêຠòàêó ðîçì³òêó, íàçèâàþòü 1-âåðøèííèì
á³ìàã³÷íèì âåðøèííèì ãðàôîì.
2. ( , )a d -ÄÈÑÒÀÍÖ²ÉÍÀ ÀÍÒÈÌÀò×ÍÀ ÐÎÇ̲ÒÊÀ ÊÎÐÎÍÈ P Pn  1
ÒÀ n-ÂÈ̲ÐÍÎÃÎ ÊÓÁÀ Qn
 [11] äîâåäåíî, ùî êîðîíà P Pn  1 íå äîïóñêຠ( , )a 1 -äèñòàíö³éíî¿ àíòè-
ìàã³÷íî¿ ðîçì³òêè äëÿ n 	 2, ÿêùî a 
 2. Óçàãàëüíèìî öåé ðåçóëüòàò íà
äîâ³ëüí³ çíà÷åííÿ a ó òàê³é òåîðåì³ .
Òåîðåìà 1. Êîðîíà P Pn  1 íå º ( , )a d -äèñòàíö³éíèì àíòèìàã³÷íèì ãðàôîì
äëÿ áóäü-ÿêèõ çíà÷åíü a ³ d .
Äîâåäåííÿ. Äëÿ êîðîíè P Pn  1 ìîæå ³ñíóâàòè ( , )a d -äèñòàíö³éíà àíòè-
ìàã³÷íà ðîçì³òêà ò³ëüêè äëÿ d 1 àáî d  2 [11]. Ïîçíà÷èìîV P Pn( ) 1 
 { }u u un n1 2 1 2, , , , , , ,    ìíîæèíó âåðøèí P Pn  1, äå { }u u un1 2, , , ³
{ }  1 2, , , n — ìíîæèíè âåðøèí êîﳿ Pn ³ n êîï³é P1 â³äïîâ³äíî. Ïðèïóñòè-
ìî, ùî ³ñíóº ( , )a d -äèñòàíö³éíà àíòèìàã³÷íà ðîçì³òêà f êîðîíè P Pn  1.
Äëÿ d 1 ìàºìî f u an ni
i
n
( )



  
1
1 [11]. Îñê³ëüêè w f ui i( ) ( )  , òî
f u w an
n n
i
i
n
i
i
n
( ) ( )
( )
 
 
 	 

1 1
1
2
 . Ç öèõ äâîõ íåð³âíîñòåé îäåðæóºìî n 
 2. Ãðà-
ôè P P P1 1 2  ³ P P P2 1 4  íå äîïóñêàþòü ( , )a 1 -äèñòàíö³éíî¿ àíòèìàã³÷íî¿
ðîçì³òêè.
Îòæå, êîðîíà P Pn  1 íå º ( , )a 1 -äèñòàíö³éíèì àíòèìàã³÷íèì ãðàôîì äëÿ
áóäü-ÿêîãî a 	 1.
Äëÿ ëàíöþãà Pn íå ³ñíóº ( , )a d -äèñòàíö³éíî¿ àíòèìàã³÷íî¿ ðîçì³òêè ïðè
a d, 	 2 [8], òîìó íåõàé n 	 3, d  2 ³ a k 2 1 — íåïàðíå ÷èñëî, äå k 	 2. Âàãè
âñ³õ âåðøèí êîðîíè P Pn  1 äëÿ ðîçì³òêè f óòâîðþþòü ìíîæèíó ç íåïàðíèõ ÷è-
ñåë. Ó öüîìó ðàç³ ì³òêàìè âåðøèí u u un1 2, , , º íåïàðí³ ÷èñëà. Öå ïðèçâîäèòü
äî òîãî, ùî âàãà w u f u f u fi i i i( ) ( ) ( ) ( )   1 1  — ïàðíå ÷èñëî äëÿ 2 1
 
 i n ,
ùî íåìîæëèâî.
̳ðêóþ÷è àíàëîã³÷íî, îäåðæóºìî, ùî äëÿ êîðîíè P Pn  1 íå ³ñíóº ( , )a 2 -äèñ-
òàíö³éíî¿ àíòèìàã³÷íî¿ ðîçì³òêè äëÿ ïàðíîãî a .
Îòæå, êîðîíà P Pn  1 íå äîïóñêຠ( , )a d -äèñòàíö³éíî¿ àíòèìàã³÷íî¿ ðîçì³òêè
äëÿ áóäü-ÿêèõ çíà÷åíü a ³ d.
Òåîðåìó äîâåäåíî.
Çíàéäåìî ôóíêö³îíàëüí³ çàëåæíîñò³, ùî ïîðîäæóþòü â³äïîâ³äíèé òèï
ðîçì³òêè äëÿ Qn , äîâ³âøè òàêó òåîðåìó.
Òåîðåìà 2. Äëÿ áóäü-ÿêîãî n 	 3 n-âèì³ðíèé êóá Qn º ( , )2 1 2
n n n   -äèñ-
òàíö³éíèì àíòèìàã³÷íèì ãðàôîì.
Äîâåäåííÿ. Ç íàñë³äêó 2 ëåìè 1 âèïëèâàº, ùî Qn äîïóñêຠ( , )a d -äèñ-
òàíö³éíó àíòèìàã³÷íó ðîçì³òêó ò³ëüêè äëÿ n 	 3.
Êîæíó âåðøèíó n-âèì³ðíîãî êóáà Qn áóäåìî ðîçãëÿäàòè ÿê n-êîìïîíåíòíèé
á³íàðíèé âåêòîð. Íåõàé ui
n — âåðøèíè Qn , äå ÷èñëî i º äåñÿòêîâèì çàïèñîì
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 2 137
á³íàðíîãî âåêòîðà ö³º¿ âåðøèíè ³ íàáóâຠçíà÷åíü
0 1 2 2 2 2 1, , , , , n n  , òîáòî V Q u u un
n n n( ) , , ,{ 0 1 2 
 , u
n
n
2 1
}.
Çàäàìî ᳺêö³þ f V Qn
n n: ( ) , , , , { }1 2 2 1 2
òàê: f u ii
n( )  1, äå i  0 1 2, , ,  , ,2 2 2 1n n  .
Ïîêàæåìî, ùî f º ( , )a d -äèñòàíö³éíîþ àíòèìà-
ã³÷íîþ ðîçì³òêîþ ãðàôà Qn .
Äîâåäåííÿ âèêîíàºìî ìåòîäîì ìàòåìàòè÷íî¿
³íäóêö³¿.
Êðîê 1. Íåõàé n  3. Äëÿ ðîçì³òêè f âåðøèíè
ui
3 , i  0 1 7, , , , îäåðæàòü ì³òêè, ÿê ïîêàçàíî íà ðèñ. 1.
Çíàéäåìî âàãè âåðøèí:
w u w u( ) , ( )0
3
1
32 3 5 10 1 4 6 11        ,
w u w u( ) , ( )2
3
3
31 4 7 12 2 3 8 13        ,
w u w u( ) , ( )4
3
5
31 6 7 14 2 5 8 15        ,
w u w u( ) , ( ) .6
3
7
33 5 8 16 4 6 7 17       
Âàãè óòâîðþþòü çðîñòàþ÷ó àðèôìåòè÷íó ïðîãðåñ³þ ç a 10, d 1, òîìó ãðàô
Q3 º (10, 1)-äèñòàíö³éíèì àíòèìàã³÷íèì.
Äëÿ ðîçì³òêè f , ÿêùî n  4, âàãè âåðøèí ìîæíà çíàéòè òàêèì ÷èíîì:
1) ÿêùî i  0 1 7, , , , òî w u w u ii i( ) ( ) ( )
4 3 32 1    ;
2) ÿêùî i  8 9 15, , .. , , òî w u w u ii i( ) ( ) ( )
4
8
3 33 2 7    

.
Ìíîæèíà âñ³õ âàã âåðøèí ãðàôà Q4 , îá÷èñëåíèõ çà ôîðìóëàìè, íàâåäåíèìè
âèùå, óòâîðþº çðîñòàþ÷ó àðèôìåòè÷íó ïðîãðåñ³þ ç ïåðøèì ÷ëåíîì a 19
³ ð³çíèöåþ d  2. Ãðàô Q4 º (19, 2)-äèñòàíö³éíèì àíòèìàã³÷íèì.
Êðîê 2. Ïðèïóñòèìî, ùî k-âèì³ðíèé êóá Qk º ( , )a d -äèñòàíö³éíèì àíòè-
ìàã³÷íèì ãðàôîì.
Êðîê 3. Äîâåäåìî, ùî Qk1 äîïóñêຠ( , )a d1 1 -äèñòàíö³éíó àíòèìàã³÷íó
ðîçì³òêó f V Qk
k k: ( ) , , , ,

 
 1
1 11 2 2 1 2{ } ç f u ii
k( )  1 1, i k 0 1 2 2 21, , , , ,
2 11k  .
Îá÷èñëèìî âàãè âåðøèí ãðàôà Qk1 çà ôîðìóëàìè:
w u w u ii
k
i
k k( ) ( ) ( ),    1 2 1 ÿêùî i k 0 1 2 1, , , ;
w u w u k ii
k
i
k k k
k
( ) ( ) ( ),

     
1
2
2 2 1 ÿêùî i k k k  2 2 1 2 11, , , .
Âàãè óòâîðþþòü ÷èñëîâó ïîñë³äîâí³ñòü a1, a d1 1 ( ), a d1 2 1 ( ),
 , ( )( )a dk1 2 1 1   , a k
k
1 2 1 ( ), a k d
k
1 2 1 1   ( ) ( ), a k
k
1 2 1  ( )
       2 1 2 1 2 1 11( ), , ( ) ( )( )d a k d
k k , äå a a k1 2 1   . Âîíà áóäå àðèôìå-
òè÷íîþ ïðîãðåñ³ºþ ç ïåðøèì ÷ëåíîì a a k1 2 1   ëèøå òîä³, êîëè äëÿ ð³çíèö³
d1 âèêîíóºòüñÿ óìîâà d d k1 1 1    . Òàêèì ÷èíîì, ãðàô Qk1 äîïóñêàº
( , )a d1 1 -äèñòàíö³éíó àíòèìàã³÷íó ðîçì³òêó ç a a
k
1 2 1   òà d k1 1 – .
Îòæå, n-âèì³ðíèé êóá Qn º ( , )a n2 -äèñòàíö³éíèì àíòèìàã³÷íèì ãðàôîì äëÿ
áóäü-ÿêîãî n 	 3. Çíàéäåìî a . Äëÿ öüîãî ñêëàäåìî ð³âíÿííÿ
n f ui
i
n
( )




0
2 1
2 2 2 11n n na d    ( ) .
138 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 2
1 2
3 4
5 6
87
Ðèñ. 1. (10, 1)-äèñòàíö³éíà àíòè-
ìàã³÷íà ðîçì³òêà ãðàôà Q3
u4
3 u5
3
u6
3 u7
3
u0
3 u1
3
u3
3u2
3
Îäåðæèìî, ùî a nn  2 1. Âèõîäèòü, ùî ãðàô Qn º ( , )2 1 2
n n n   -äèñ-
òàíö³éíèì àíòèìàã³÷íèì äëÿ áóäü-ÿêîãî n 	 3.
Òåîðåìó äîâåäåíî.
Ç äîâåäåííÿ ö³º¿ òåîðåìè âèïëèâàº, ùî ìíîæèíà âñ³õ âàã âåðøèí Qn óòâî-
ðþº çðîñòàþ÷ó àðèôìåòè÷íó ïðîãðåñ³þ, ³ âåðøèí³ ç ìåíøîþ ì³òêîþ â³äïîâ³äàº
ìåíøà âàãà. Òîìó ñïðàâåäëèâèì º òàêèé íàñë³äîê.
Íàñë³äîê 1. Äëÿ áóäü-ÿêîãî n 	 3 n-âèì³ðíèé êóá Qn º âïîðÿäêîâàíèì
( , )2 1 2n n n   -äèñòàíö³éíèì àíòèìàã³÷íèì ãðàôîì.
3. ÏÐÎ 1-ÂÅÐØÈÍÍÓ Á²ÌÀò×ÍÓ ÂÅÐØÈÍÍÓ ÐÎÇ̲ÒÊÓ
ÃÐÀԲ ÎÊÐÅÌÈÕ ÊÎÍÑÒÐÓÊÖ²É
Äîñë³äæåííÿ ðåáåðíî-á³ìàã³÷íèõ ãðàô³â ðîçïî÷àëîñÿ ó 2004 ðîö³. Öåé òèï
ðîçì³òêè ââåäåíî àâòîðàìè ðîáîòè [13], à ó 2014 ðîö³ çàïðîïîíîâàíî 1-âåð-
øèííó á³ìàã³÷íó âåðøèííó ðîçì³òêó [12]. Ö³ âèäè ðîçì³òîê º ö³êàâèìè äëÿ
ãðàô³â, ÿê³ íå ìàþòü ðåáåðíî¿ àáî âåðøèííî¿ ìàã³÷íî¿ ðîçì³òêè. Àëå ïèòàííÿ
íàÿâíîñò³ ãðàô³â, ùî íå äîïóñêàþòü á³ìàã³÷íèõ ðîçì³òîê, òàêîæ º àêòóàëüíèì
³ ïîâ’ÿçàíå ç ³íôîðìàö³ºþ ïðî ñòðóêòóðí³ âëàñòèâîñò³ ãðàô³â.
Òåîðåìà 3. Áóäü-ÿêèé ãðàô, ÿêèé ì³ñòèòü á³ëüøå äâîõ âåðøèí ñòåïåíÿ îäè-
íèöÿ, íå º 1-âåðøèííèì á³ìàã³÷íèì âåðøèííèì ãðàôîì.
Äîâåäåííÿ. Äîñòàòíüî ðîçãëÿíóòè ãðàô G, ÿêèé
ì³ñòèòü òðè âåðøèíè ñòåïåíÿ îäèíèöÿ, ÿê çîáðàæåíî
íà ðèñ. 2. Íå îáîâ’ÿçêîâî, ùîá G áóâ çâ’ÿçíèì ãðàôîì.
Ïðèïóñòèìî, ùî ³ñíóº 1-âåðøèííà á³ìàã³÷íà âåðøèííà
ðîçì³òêà f äëÿ G , òîáòî âàãà êîæíî¿ âåðøèíè
äîð³âíþº îäíîìó ç äâîõ ð³çíèõ ÷èñåë, ùî º ìàã³÷íèìè
ñòàëèìè äëÿ f . Öå ïðèçâîäèòü äî òîãî, ùî ñåðåä âàã
w f u( ) ( )1 1 , w f u( ) ( ) 2 2 , w f u( ) ( ) 3 3 º îäíà-
êîâ³. Öå íåìîæëèâî, îñê³ëüêè f — ᳺêö³ÿ. Îòæå, ãðàô,
ùî ì³ñòèòü á³ëüøå äâîõ âåðøèí ñòåïåíÿ îäèíèöÿ, íå äîïóñêຠ1-âåðøèííî¿
á³ìàã³÷íî¿ âåðøèííî¿ ðîçì³òêè.
Òåîðåìó äîâåäåíî.
Òåîðåìà 3 äຠçìîãó âèêëþ÷èòè ç äîñë³äæåííÿ áàãàòî ð³çíèõ òèï³â ãðàô³â.
Äî íèõ íàëåæàòü âñ³ äåðåâà, â³äì³íí³ â³ä ëàíöþã³â. Íàïðèêëàä, êîðîíà P Pn  1 íå
º 1-âåðøèííèì á³ìàã³÷íèì âåðøèííèì ãðàôîì äëÿ n 	 3.
Òåîðåìà 4. Íåõàé ó ãðàô³ G º âåðøèíè u V Gi  ( ), i 	 3, äëÿ ÿêèõ deg ( )ui  2.
ßêùî N u ui
i
( ) 
	
{ }
3

, u ui  , òî G íå º 1-âåðøèííèì á³ìàã³÷íèì âåðøèííèì ãðàôîì.
Äîâåäåííÿ. Ðîçãëÿíåìî ãðàô G, ùî çàäîâîëüíÿº âèìîãè óìîâè òåîðåìè 4.
Íåõàé ᳺêö³ÿ f ç ìíîæèíè V G( ) íà ìíîæèíó { }1 2, , , | | V º 1-âåðøèííîþ
á³ìàã³÷íîþ âåðøèííîþ ðîçì³òêîþ G. Âåðøèíè u, ui ,  i V G ( ), äå i  1 2 3, , , ,
deg ( )ui  2 , ïîðîäæóþòü ï³äãðàô ãðàôà G, ³ êîæíà ïîñë³äîâí³ñòü âåðøèí u, ui ,  i
óòâîðþº ëàíöþã. Îñê³ëüêè w u f u fi i( ) ( ) ( )   , òî ç áóäü-ÿêèõ òðüîõ âåðøèí ui
äëÿ äâîõ âàãè çá³ãàþòüñÿ, íàïðèêëàä w u w us t( ) ( ) , s t . Öå íåìîæëèâî, îñê³ëüêè
f fs t( ) ( )  . Òîìó ïðèïóùåííÿ º õèáíèì. Ãðàô G íå äîïóñêຠ1-âåðøèííî¿
á³ìàã³÷íî¿ âåðøèííî¿ ðîçì³òêè.
Òåîðåìó äîâåäåíî.
Òåîðåìà 5. Êóá Q3 íå º 1-âåðøèííèì á³ìàã³÷íèì âåðøèííèì ãðàôîì.
Äîâåäåííÿ. Ïîçíà÷èìî V Q u u u u u u u u( ) , , , , , , ,3 0 1 2 3 4 5 6 7 { } ìíîæèíó âåð-
øèí Q3 òàêèì ÷èíîì, ùî äëÿ âåðøèíè ui ÷èñëî i º äåñÿòêîâèì çàïèñîì á³íàðíî-
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 2 139
u2
u1
u3
1
2
3
Ðèñ. 2. Ãðàô G
ãî âåêòîðà ö³º¿ âåðøèíè, äå i  0 1 2 7, , , , . Çàäàìî ᳺêòèâíå â³äîáðàæåííÿ
f V Q: ( ) , , ,3 1 2 8 { }. Ïðèïóñòèìî, ùî f — 1-âåðøèííà á³ìàã³÷íà âåðøèííà
ðîçì³òêà Q3 . Îòæå, âàãè âåðøèí äîð³âíþþòü ñòàëèì k1 àáî k2 . Äëÿ u0 , u3 ³ u5
îäåðæèìî
w u f u f u f u( ) ( ) ( ) ( )0 1 2 4   ,
w u f u f u f u( ) ( ) ( ) ( )3 1 2 7   ,
w u f u f u f u( ) ( ) ( ) ( )5 1 4 7   .
Ç öèõ òðüîõ ÷èñåë äâà ïîâèíí³ áóòè ð³âíèìè ì³æ ñîáîþ, àëå öå íåìîæëèâî,
îñê³ëüêè f — ᳺêö³ÿ. Òàêèì ÷èíîì, ãðàô Q3 íå º 1-âåðøèííèì á³ìàã³÷íèì
âåðøèííèì.
Òåîðåìó äîâåäåíî.
Íàñë³äîê 1. ßêùî ãðàô G ì³ñòèòü Q3 ÿê êîìïîíåíòó, òî G íå º 1-âåðøèííèì
á³ìàã³÷íèì âåðøèííèì ãðàôîì.
Äîâåäåííÿ âèïëèâຠáåçïîñåðåäíüî ç òåîðåìè 5.
Òåîðåìà 6. ßêùî ðåãóëÿðíèé ãðàô G äîïóñêຠäèñòàíö³éíó ìàã³÷íó
ðîçì³òêó, òî ãðàô G G º 1-âåðøèííèì á³ìàã³÷íèì âåðøèííèì.
Äîâåäåííÿ. Íåõàé g — äèñòàíö³éíà ìàã³÷íà ðîçì³òêà r-ðåãóëÿðíîãî ãðàôà G
ïîðÿäêó n, ³ êîæíà éîãî âåðøèíà ìຠâàãó, ùî äîð³âíþº ñòàë³é k. Ïîçíà÷èìî
V u u un n  { }1 2 1 2, , , , , , ,   ìíîæèíó âåðøèí G G , äå ui ,  i — âåðøèíè
ð³çíèõ êîìïîíåíò ó öüîìó ãðàô³ òà ui ,  i º îáðàçàìè âåðøèíè x V Gi  ( ),
i n 1 2, , , . Äëÿ G G çàäàìî ᳺêòèâíó ôóíêö³þ f V n: , , , { }1 2 2 òàê:
f u g xi i( ) ( ) , f g x ni i( ) ( )   .
Òîä³ âåðøèíè G G îäåðæàòü âàãè: w u w x kf i g i( ) ( )   const , w f i( ) 
    w x nr k nrg i( ) const . Îòæå, ðîçì³òêà f ãðàôà G G º 1-âåðøèííîþ
á³ìàã³÷íîþ âåðøèííîþ.
Òåîðåìó äîâåäåíî.
ÂÈÑÍÎÂÊÈ
Ó ñòàòò³ âèêëàäåíî ðåçóëüòàòè òåîðåòè÷íèõ äîñë³äæåíü ùîäî íàÿâíîñò³
( , )a d -äèñòàíö³éíî¿ àíòèìàã³÷íî¿ ³ 1-âåðøèííî¿ á³ìàã³÷íî¿ âåðøèííî¿ ðîçì³òîê
äëÿ îêðåìèõ òèï³â ãðàô³â. Óçàãàëüíåíî ðåçóëüòàòè äëÿ êîðîíè P Pn  1, ÿê³ äà-
þòü çìîãó ñòâåðäæóâàòè, ùî P Pn  1 íå º ( , )a d -äèñòàíö³éíèì àíòèìàã³÷íèì
ãðàôîì äëÿ áóäü-ÿêèõ çíà÷åíü a ³ d. Çàïðîïîíîâàíî ñïîñ³á çíàõîäæåííÿ
( , )a d -äèñòàíö³éíî¿ àíòèìàã³÷íî¿ ðîçì³òêè n-âèì³ðíîãî êóáà Qn . Ðîçãëÿíóòî ïè-
òàííÿ íàÿâíîñò³ ãðàô³â, ùî íå äîïóñêàþòü 1-âåðøèííî¿ á³ìàã³÷íî¿ âåðøèííî¿
ðîçì³òêè. Âèÿâëåíî çâ’ÿçîê äèñòàíö³éíî¿ ìàã³÷íî¿ ðîçì³òêè ðåãóëÿðíîãî ãðàôà
G ç 1-âåðøèííîþ á³ìàã³÷íîþ âåðøèííîþ ðîçì³òêîþ G G .
ÑÏÈÑÎÊ Ë²ÒÅÐÀÒÓÐÈ
1. Gallian J.A. A dynamic survey of graph labeling. The Electronic Journal of Combinatorics. 2016.
DS6: Dec 23.
2. Stewart B.M. Magic graphs. Canad. J. Math. 1966. Vol. 18. P. 1031–1059.
3. Stanley R. Linear homogeneous Diophantine equations and magic labelings of graphs. Duke Math. J.
1973. Vol. 40. P. 607–632.
4. Bloom G.S., Golomb S.W. Numbered complete graphs, unusual rulers and assorted applications.
Theory and applications of graphs. Lecture Notes in Math. New York: Springer-Verlag, 1978.
Vol. 642. P. 53–65.
140 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 2
5. Froncek D. Fair incomplete tournaments with odd number of teams and large number of games.
Congressus Numerantium. 2007. Vol. 187, Iss. 1. P. 83–89.
6. Mathematics and sports: Gallian J. A. (ed). Mathematical Association of America. 2010. 338 p.
7. Froncek D. Handicap distance antimagic graphs and incomplete tournaments. AKCE Int. J. Graphs
Comb. 2013. Vol. 10, N 2. P. 119–127.
8. Arumugam S., Kamatchi N. On (a; d)-distance antimagic graphs. Australasian Journal of
Combinatorics. 2012. Vol. 54. P. 279–287.
9. Nalliah M. Antimagic labelings of graphs and digraphs: Ph. D. Thesis. The National Centre for
Advanced Research in Discrete Mathematics, University of Kalasalingam. 2014.
10. Ñåìåíþòà Ì.Ô. Ïðî äèñòàíö³éíó àíòèìàã³÷íó ðîçì³òêó ãðàô³â. Òåîð³ÿ îïòèìàëüíèõ ð³øåíü.
Êè¿â: ²í-ò ê³áåðíåòèêè ³ì. Â.Ì. Ãëóøêîâà ÍÀÍ Óêðà¿íè, 2016. Ñ. 26–32.
11. Ñåìåíþòà Ì.Ô. ( , )a d -äèñòàíö³éíà àíòèìàã³÷íà ðîçì³òêà îêðåìèõ òèï³â ãðàô³â. Êèáåðíåòèêà
è ñèñòåìíûé àíàë³ç. 2016. Ò. 52, ¹ 4. Ñ. 135–142.
12. Baskar Babujee J., Babitha S. On 1-vertex bimagic vertex labeling. Tamkang Journal of
Mathematics. 2014. Vol. 45, N 3. P. 259–273.
13. Baskar Babujee J. Bimagic labeling in path graphs. The Mathematics Education. 2004. Vol. 38, N 1.
P. 12–16.
Íàä³éøëà äî ðåäàêö³¿ 10.05.2017
Ì.Ô. Ñåìåíþòà
Î ( , )a d -ÄÈÑÒÀÍÖÈÎÍÍÎÉ ÀÍÒÈÌÀÃÈ×ÅÑÊÎÉ È 1-ÂÅÐØÈÍÍÎÉ ÁÈÌÀÃÈ×ÅÑÊÎÉ
ÂÅÐØÈÍÍÎÉ ÐÀÇÌÅÒÊÀÕ ÎÏÐÅÄÅËÅÍÍÛÕ ÒÈÏÎÂ ÃÐÀÔÎÂ
Àííîòàöèÿ. Îáîáùåíû ðåçóëüòàòû äëÿ êîðîíû P Pn  1, êîòîðûå äàþò âîç-
ìîæíîñòü óòâåðæäàòü, ÷òî P Pn  1 íå ÿâëÿåòñÿ ( , )a d -äèñòàíöèîííûì àíòèìàãè-
÷åñêèì ãðàôîì äëÿ ëþáûõ çíà÷åíèé a è d. Ïîëó÷åíî óñëîâèå ñóùåñòâîâàíèÿ
( , )a d -äèñòàíöèîííîé àíòèìàãè÷åñêîé ðàçìåòêè ãèïåðêóáà Qn . Íàéäåíû ôóíê-
öèîíàëüíûå çàâèñèìîñòè, ïîðîæäàþùèå ýòîò òèï ðàçìåòêè äëÿ Qn . Ìåòîäîì
ìàòåìàòè÷åñêîé èíäóêöèè äîêàçàíî, ÷òî Qn ÿâëÿåòñÿ ( , )2 1 2
n n n   -äèñòàí-
öèîííûì àíòèìàãè÷åñêèì ãðàôîì. Îïðåäåëåíû òðè òèïà ãðàôîâ, íå äîïóñêà-
þùèõ 1-âåðøèííîé áèìàãè÷åñêîé âåðøèííîé ðàçìåòêè. Óñòàíîâëåíà ñâÿçü
äèñòàíöèîííîé ìàãè÷åñêîé ðàçìåòêè ðåãóëÿðíîãî ãðàôà G ñ 1-âåðøèííîé áè-
ìàãè÷åñêîé âåðøèííîé ðàçìåòêîé G G .
Êëþ÷åâûå ñëîâà: äèñòàíöèîííàÿ ìàãè÷åñêàÿ ðàçìåòêà, ( , )a d -äèñòàíöèîííàÿ
àíòèìàãè÷åñêàÿ ðàçìåòêà, 1-âåðøèííàÿ áèìàãè÷åñêàÿ âåðøèííàÿ ðàçìåòêà,
n-ìåðíûé êóá, êîðîíà.
Ì.F. Semeniuta
ON ( , )a d -DISTANCE ANTIMAGIC AND 1-VERTEX BIMAGIC VERTEX LABELINGS
OF CERTAIN TYPES OF GRAPHS
Abstract. We have generalized the results for corona P Pn  1, which make it
possible to state that P Pn  1 is not an ( , )a d -distance antimagic graph for all a
and d. We have obtained the condition for the existence of an ( , )a d -distance
antimagic labeling of a hypercube Qn . We found functional relationships that
generate this type of labeling for Qn and used the method of mathematical
induction to prove that Qn is a ( , )2 1 2
n n n   -distance antimagic graph. We
have defined two types of graphs that do not allow 1-vertex bimagic vertex
labeling. We also established a relation between the distance magic labeling of
a regular graph G with 1-vertex bimagic vertex labeling G G .
Keywords: distance magic labeling, ( , )a d -distance antimagic labeling, 1-vertex
bimagic vertex labeling, n-dimensional cube, crown.
Ñåìåíþòà Ìàðèíà Ôðîë³âíà,
êàíäèäàò ô³ç.-ìàò. íàóê, äîöåíò êàôåäðè Ëüîòíî¿ àêàäå쳿 Íàö³îíàëüíîãî àâ³àö³éíîãî óí³âåðñèòåòó,
Êðîïèâíèöüêèé, e-mail: marina_semenyuta@ukr.net.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 2 141