Nonexistence of some T-factorizations of order 12
We investigate the Beineke problem of the existence of T-factorizations of complete graphs and prove several theorems on the existence of T-factorizations. Using these theorems, we establish the nonexistence of T-factorizations for 32 nonisomorphic admissible trees of order 12.
Saved in:
| Date: | 2006 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Ukrainian English |
| Published: |
Institute of Mathematics, NAS of Ukraine
2006
|
| Online Access: | https://umj.imath.kiev.ua/index.php/umj/article/view/3484 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Ukrains’kyi Matematychnyi Zhurnal |
| Download file: |  |
Institution
Ukrains’kyi Matematychnyi Zhurnal| _version_ | 1860509581875085312 |
|---|---|
| author | Petrenyuk, A. Ya. Петренюк, А. Я. |
| author_facet | Petrenyuk, A. Ya. Петренюк, А. Я. |
| author_sort | Petrenyuk, A. Ya. |
| baseUrl_str | https://umj.imath.kiev.ua/index.php/umj/oai |
| collection | OJS |
| datestamp_date | 2020-03-18T19:55:42Z |
| description | We investigate the Beineke problem of the existence of T-factorizations of complete graphs and prove several theorems on the existence of T-factorizations. Using these theorems, we establish the nonexistence of T-factorizations for 32 nonisomorphic admissible trees of order 12. |
| first_indexed | 2026-03-24T02:43:23Z |
| format | Article |
| fulltext |
UDK 519.1
A. Q. Petrengk (DerΩ. l\ot. akad. Ukra]ny, Kirovohrad)
NEISNUVANNQ DEQKYX T-FAKTORYZACIJ PORQDKU 12
We investigate the Beineke problem of the existence of T-factorizations of complete graphs. We prove
some theorems on the nonexistence of T-factorizations. By using these theorems, we establish the
nonexistence of T-factorizations for 32 nonisomorphic admissible trees of order 12.
DoslidΩu[t\sq zadaça L. Bajneke pro isnuvannq T-faktoryzacij povnyx hrafiv. Dovedeno
kil\ka teorem pro isnuvannq T-faktoryzacij; z ]x dopomohog vstanovleno neisnuvannq T-
faktoryzacij dlq 32 neizomorfnyx dopustymyx derev porqdku 12.
1. Formulgvannq zadaçi ta rezul\taty poperednykiv. Nexaj T — derevo
porqdku 12, K n —1povnyj hraf toho Ω porqdku. T-faktoryzaci[g hrafa K n
nazyvagt\ taku sukupnist\ derev { T1 , T2 , … , Tk }, wo: 1) vsi Ti izomorfni de-
revu T; 2) vsi Ti — pidhrafy hrafa K n i 3) koΩne rebro hrafa K n naleΩyt\
odnomu i til\ky odnomu z derev T1 , T2 , … , Tk . Zadaça polqha[ v tomu, wob pry
zadanomu n dlq koΩnoho dereva T porqdku n z’qsuvaty, isnu[ T-faktoryza-
ciq hrafa K n çy ni.
Cg zadaçu (zadaçu isnuvannq T-faktoryzacij) postavyv L. Bajneke ·1‚ u
1964 r. Vin vstanovyv, wo neobxidnymy umovamy isnuvannq T-faktoryzaci] po-
rqdku n [ parnist\ çysla n, n = 2k, ta vykonannq nerivnosti ∆ ( T ) ≤ k, de ∆ ( T )
— najvywyj stepin\ verßyny u derevi T. Dereva, wo zadovol\nqgt\ umovy
Bajneke, nazyvagt\ dopustymymy.
Í. Xuanh ta A. Rosa ·2‚ u 1978 r. rozv’qzaly zadaçu isnuvannq T-faktoryza-
cij dlq vsix n ≤ 8. A. Q. Petrengk ·3, 4‚ rozv’qzav ]] u vypadku n = 10 ta, za
vynqtkom 20 derev, u vypadku n = 14. Dvi vaΩlyvi obstavyny zabezpeçyly uspix
u vypadkax n = 10 ta n = 14: zruçni neobxidni umovy isnuvannq T-faktoryza-
cij, znajdeni avtorom statej ·3, 4‚, ta bicykliçnyj metod pobudovy T-faktory-
zacij, z dopomohog qkoho oderΩano pozytyvni rezul\taty isnuvannq.
U cij statti doslidΩu[t\sq zadaça isnuvannq T-faktoryzacij porqdku 12. U
c\omu vypadku bicykliçnyj metod pobudovy ne pracg[ ·3, 4‚. Tomu na moment ]]
napysannq bulo vidomo lyße 20 derev porqdku 12, dlq qkyx isnugt\ T-fakto-
ryzaci]. Ci T-faktoryzaci] pobudovano pivobertovym metodom u statti ·5‚.
NyΩçe my navodymo rqd rezul\tativ pro neisnuvannq T-faktoryzacij po-
rqdku 12, zastosovugçy vidomi ta znaxodqçy novi neobxidni umovy ]x isnuvannq.
2. Neisnuvannq deqkyx T-faktoryzacij porqdku 12. Nexaj T — dopus-
tyme derevo porqdku 12. Poznaçymo çerez d ( T ) = ( d1 , d2 , d3 , d4 , d5 , d6 ) vek-
tor, de di —1kil\kist\ verßyn stepenq i u derevi T. Zaznaçymo, wo u roboti ·6‚
znajdeno try seri] zahal\nyx neobxidnyx umov isnuvannq T-faktoryzacij u
terminax komponent vektora d, dvi z qkyx u vypadku n = 12 magt\ vyhlqd
d2 ≥ d5, d2 + 2d3 ≥ d4. (1)
Perehlqnuvßy spysok derev porqdku 12, my vstanovyly, wo u n\omu [ toçno
11 derev, dlq qkyx umovy (1) ne vykonugt\sq i, otΩe, vidpovidni ]m T-faktory-
zaci] ne isnugt\. Ci dereva navedeno u tabl. 1.
U perßomu stovpci mistqt\sq vektory d derev, qki pereliçugt\sq u tre-
t\omu stovpci i numerugt\sq u druhomu, a v ostann\omu stovpci vkazu[t\sq,
vnaslidok nevykonannq qko] z dvox umov (1) vidpovidne derevo ne dopuska[ T-
faktoryzaci].
© A. Q. PETRENGK, 2006
666 ISSN 1027-3190. Ukr. mat. Ωurn., 2006, t. 58, # 5
NEISNUVANNQ DEQKYX T-FAKTORYZACIJ PORQDKU 12 667
3. Nova neobxidna umova isnuvannq T-faktoryzacij porqdku 12. Pry-
pustymo, wo isnu[ T-faktoryzaciq Φ hrafa K 12 . Typom verßyny x hrafa
K 12 u T-faktoryzaci] Φ nazyvagt\ vektor t ( x ) = ( α1 , α2 , α3 , α4 , α5 , α6 ) , de
αi — kil\kist\ komponent T-faktoryzaci] Φ, dlq qkyx x [ verßynog stepenq
i, i = 1, … , 6. Oçevydno, wo
α1 + α2 + α3 + α4 + α5 + α6 = 6 (2)
ta
α1 + 2α2 + 3α3 + 4α4 + 5α5 + 6α6 = 11. (3)
Tablycq 1
d N T Umova, wo ne
vykonu[t\sq
8 0 3 0 1 0
8 1 0 3 0 0
9 0 0 2 1 0
9 0 1 0 2 0
1
2
3
4
5
6
7
8
9
10
11
12 13 14 15 16 27 28 39 3A 4B 4C
27 28 39 3A 7B 7C
27 28 79 7A 8B 8C
27 28 79 7A 9B 9C
12 13 14 15 26 27 28 39 3A 3B 4C
26 27 28 39 3A 3B 6C
26 27 28 39 9A 9B 9C
12 13 14 15 16 27 28 29 3A 3B 3C
27 28 79 7A 7B 7C
27 28 29 2A 3B 3C
27 28 79 7A 7B 7C
Perßa
Druha
Obydvi
Perßa
Qk vkazano v ·3‚, systema rivnqn\ (2), (3) ma[ 7 rozv’qzkiv u cilyx nevid’[mnyx
çyslax, qki [ moΩlyvymy typamy verßyn u T -faktoryzaciqx porqdku 12. Ci
typy t 1 , t 2 , t 3 , t 4 , t 5 , t 6 , t 7 navedeno u tabl. 2.
Tablycq 2
α t 1 t 2 t 3 t 4 t 5 t 6 t 7
α1
α2
α3
α4
α5
α6
1 2 3 3 4 4 5
5 3 1 2 0 1 0
0 1 2 0 1 0 0
0 0 0 1 1 0 0
0 0 0 0 0 1 0
0 0 0 0 0 0 1
Nexaj T-faktoryzaciq Φ mistyt\ βj verßyn typu tj
, j = 1, … , 7. Vektor
ββββ ( Φ ) = ( β1 , β2 , β3 , β4 , β5 , β6 , β7 ) budemo nazyvaty typom T-faktoryzaci]
Φ. Oçevydno,
β1 + β2 + β3 + β4 + β5 + β6 + β7 = 12. (4)
Pidraxovugçy dvoma riznymy sposobamy zahal\ni kil\kosti verßyn stepenq j
dlq koΩnoho j = 1, … , 6 u komponentax T-faktoryzaci] Φ, otrymu[mo taki
spivvidnoßennq:
ISSN 1027-3190. Ukr. mat. Ωurn., 2006, t. 58, # 5
668 A. Q. PETRENGK
β1 + 2β2 + 3β3 + 3β4 + 4β5 + 4β6 + 5β7 = 6 d1,
5β1 + 3β2 + β3 + 2β4 + β6 = 6 d2,
β2 + 2β3 + β5 = 6 d3,
(5)
β4 + β5 = 6 d4,
β6 = 6 d5,
β7 = 6 d6.
Sformulg[mo oderΩanyj rezul\tat u vyhlqdi teoremy.
Teorema 1. Dlq isnuvannq T-faktoryzacij porqdku n = 12 u vypadku, ko-
ly d ( T ) = ( d1 , d2 , d3 , d4 , d5 , d6 ), neobxidno, wob systema (4), (5) dopuskala
rozv’qzky u cilyx nevid’[mnyx çyslax.
Cg pryncypovo vaΩlyvu teoremu oderΩano, v bil\ß zahal\nomu vyhlqdi,
u1statti ·3‚. My zastosu[mo ]] dlq dovedennq neisnuvannq T-faktoryzacij dlq
pevnyx klasiv derev porqdku 12, wo ne vklgçagt\ derev iz tabl. 1.
Rozv’qzky systemy (4), (5) u cilyx nevid’[mnyx çyslax vyznaçagt\ dopustymi
typy T-faktoryzacij z d ( T ) = ( d1 , d2 , d3 , d4 , d5 , d6 ).
4. Zastosuvannq neobxidno] umovy. Poznaçennq i → i + m × j budemo
rozumity qk zaminu rivnqnnq i u deqkij systemi rivnqn\ sumog rivnqnnq i ta
pomnoΩenoho na m rivnqnnq j. Vykonugçy elementarni peretvorennq systemy
(4), (5)
2 → 2 – 1 × 1, 3 → 3 – 5 × 1,
1 → 1 – 1 × 2, 3 → 3 + 2 × 2, 4 → 4 – 1 × 2,
1 → 1 – 1 × 3, 2 → 2 + 2 × 3, 4 → 4 + 2 × 3, 5 → 5 – 1 × 3,
1 → 1 + 1 × 6, 2 → 2 – 1 × 6, 3 → 3 – 2 × 6, 4 → 4 – 1 × 6, 5 → 5 + 2 × 6,
1 → 1 + 2 × 7, 2 → 2 + 2 × 7, 3 → 3 – 3 × 7, 4 → 4 – 2 × 7, 5 → 5 + 2 × 7,
znaxodymo zahal\nyj rozv’qzok ci[] systemy u dijsnyx çyslax (p, q — para-
metry):
β1 = 6d1 + 6d2 – 60 + p + q,
β2 = 6d3 – 2p – q,
β3 = p,
β4 = 6d4 – q,
β5 = q,
β6 = 6d5,
β7 = 6d6.
Znajdenyj rozv’qzok ma[ misce pry takyx umovax sumisnosti systemy:
5d1 + 4d2 + 3d3 + 2d4 + d5 = 50,
4d1 + 3d2 + 2d3 + d4 – d6 = 38.
My vstanovyly, wo vektor d koΩnoho z dopustymyx derev porqdku 12 zado-
vol\nq[ umovy sumisnosti, tomu v podal\ßomu ci umovy moΩna ne braty do
uvahy.
ISSN 1027-3190. Ukr. mat. Ωurn., 2006, t. 58, # 5
NEISNUVANNQ DEQKYX T-FAKTORYZACIJ PORQDKU 12 669
Tablycq 3
∆ d nd nt ββββ
2
3
4
2 10 0 0 0 0
3 8 1 0 0 0
4 6 2 0 0 0
5 4 3 0 0 0
6 2 4 0 0 0
7 0 5 0 0 0
4 7 0 1 0 0
5 5 1 1 0 0
6 3 2 1 0 0
1
10
42
54
23
2
11
59
72
1
4
7
4
1
0
1
16
16
12 0 0 0 0 0 0
6 6 0 0 0 0 0
7 4 1 0 0 0 0
8 2 2 0 0 0 0
9 0 3 0 0 0 0
0 12 0 0 0 0 0
1 10 1 0 0 0 0
2 8 2 0 0 0 0
3 6 3 0 0 0 0
4 4 4 0 0 0 0
5 2 5 0 0 0 0
6 0 6 0 0 0 0
10 6 6 0 0 0 0
1 4 7 0 0 0 0
2 2 8 0 0 0 0
3 0 9 0 0 0 0
0 0 12 0 0 0 0
—
6 0 0 6 0 0 0
0 6 0 6 0 0 0
0 1 4 6 0 0 0
1 5 0 5 1 0 0
2 2 2 6 0 0 0
2 3 1 5 1 0 0
2 4 0 4 2 0 0
3 0 3 6 0 0 0
3 1 2 5 1 0 0
3 2 1 4 2 0 0
3 3 0 3 3 0 0
4 2 0 2 4 0 0
4 1 1 3 3 0 0
4 2 0 2 4 0 0
5 0 1 2 4 0 0
6 1 0 1 5 0 0
6 0 0 0 6 0 0
0 0 6 6 0 0 0
0 1 5 5 1 0 0
0 2 4 4 2 0 0
0 3 3 3 3 0 0
0 4 2 2 4 0 0
0 5 1 1 5 0 0
0 6 0 0 6 0 0
1 0 5 4 2 0 0
1 1 4 3 3 0 0
1 2 3 2 4 0 0
1 3 2 1 5 0 0
ISSN 1027-3190. Ukr. mat. Ωurn., 2006, t. 58, # 5
670 A. Q. PETRENGK
Zakinçennq tabl. 3
∆ d nd nt ββββ
4
5
6
6 4 0 2 0 0
7 1 3 1 0 0
7 2 1 2 0 0
8 0 2 2 0 0
8 1 0 3 0 0
5 6 0 0 1 0
6 4 1 0 1 0
7 2 2 0 1 0
7 3 0 1 1 0
8 0 3 0 1 0
8 1 1 1 1 0
8 2 0 0 2 0
9 0 0 2 1 0
9 0 1 0 2 0
6 5 0 0 0 1
7 3 1 0 0 1
8 1 2 0 0 1
8 2 0 1 0 1
9 0 1 1 0 1
9 1 0 0 1 1
10 0 0 0 0 2
18
20
28
6
3
10
35
28
17
4
15
5
2
2
7
17
8
8
3
3
1
1
1
1
1
0
1
4
1
1
0
1
1
0
0
1
4
1
1
1
1
1
1 4 1 0 6 0 0
2 0 4 2 4 0 0
2 1 3 1 5 0 0
2 2 2 0 6 0 0
3 0 3 0 6 0 0
0 0 0 12 0 0 0
0 0 6 0 6 0 0
0 0 0 6 6 0 0
0 0 0 0 12 0 0
—
6 0 0 0 0 6 0
0 6 0 0 0 6 0
1 4 1 0 0 6 0
2 2 2 0 0 6 0
3 0 3 0 0 6 0
0 0 6 0 0 6 0
0 0 0 6 0 6 0
—
0 0 0 0 6 6 0
0 0 0 0 0 12 0
—
—
6 0 0 0 0 0 6
0 6 0 0 0 0 6
1 4 1 0 0 0 6
2 2 2 0 0 0 6
3 0 3 0 0 0 6
0 0 6 0 0 0 6
0 0 0 6 0 0 6
0 0 0 0 6 0 6
0 0 0 0 0 6 6
0 0 0 0 0 0 12
U tabl. 3 navedeno spysky dopustymyx typiv T-faktoryzacij porqdku 12,
otrymanyx za dopomohog neskladnyx komp’gternyx obçyslen\. Perßyj stov-
pec\ vmiwu[ znaçennq funkci] ∆ rozhlqnutyx derev, druhyj — d-vektory, tre-
tij —1kil\kist\ neizomorfnyx derev iz vkazanym vektorom d, çetvertyj —
kil\kist\ dopustymyx typiv T-faktoryzacij dlq c\oho Ω znaçennq d. Nareßti,
v ostann\omu stovpci pereliçeno vsi dopustymi typy T-faktoryzacij. Proçerk
u stovpci ββββ vkazu[ na neisnuvannq dopustymyx typiv dlq derev z vidpovidnym
znaçennqm d.
Z ci[] tablyci vyplyva[ neisnuvannq T-faktoryzacij dlq 2 derev porqdku112.
Ci dereva navedeno u tabl. 4, struktura qko] analohiçna strukturi tabl.11.
ISSN 1027-3190. Ukr. mat. Ωurn., 2006, t. 58, # 5
NEISNUVANNQ DEQKYX T-FAKTORYZACIJ PORQDKU 12 671
Tablycq 4
d N T
7 0 5 0 0 0 12
13
37 38 49 4A 5B 6C
37 38 59 5A 7B 7C
U zv’qzku z vykladenym vywe sformulg[mo nastupnu zadaçu, wo pohlyblg[
zadaçu pro isnuvannq T-faktoryzacij.
Zadaça 1. Dlq koΩnoho dereva T porqdku 12 z d ( T ) = ( d1 , d2 , d3 , d4 , d5 ,
d6 ) vkazaty mnoΩynu realizovnyx typiv, tobto mnoΩynu tyx dopustymyx typiv,
qki realizugt\sq vidpovidnymy T-faktoryzaciqmy. Analohiçnu zadaçu moΩna
sformulgvaty dlq koΩnoho porqdku n = 2k ≥ 10.
5. Podal\ßi teoremy pro neisnuvannq. Dovedemo kil\ka zahal\nyx re-
zul\tativ pro neisnuvannq T -faktoryzacij ta z ]x dopomohog vydilymo rqd de-
rev porqdku 12, dlq qkyx T-faktoryzaci] nemoΩlyvi.
Sprutom porqdku n = 2k nazvemo derevo T porqdku n z [dynog verßynog
stepenq ∆ ( T ) = k (cg verßynu nazyvatymemo centrom spruta), stepeni vsix
inßyx verßyn qkoho ne perevywugt\ 2. Sprut porqdku 2k nazvemo ( 2k, s ) -
sprutom, qkwo rivno s joho kincevyx verßyn ne sumiΩni z centrom. Lancghy,
qki z’[dnugt\ centr spruta z ne sumiΩnymy z nym kincevymy verßynamy, budemo
nazyvaty wupal\cqmy spruta. Oçevydno, wo s < k.
Teorema 2. Qkwo T — ( 2k, s ) -sprut takyj, wo s < k – 1, to T-fakto-
ryzaci] ne isnugt\.
Dovedennq. Zrozumilo, wo u vypadku spruta T porqdku 2k ma[mo d ( T ) =
= ( k, k – 1, … , 0, 1 ). Prypustymo protyleΩne tverdΩenng teoremy, tobto isnu[
T-faktoryzaciq Φ. Todi k verßyn hrafa K n magt\ typ ( k – 1, 0, … , 0, 1 ), a
inßi k verßyn — typ ( 1, k – 1, … , 0 ). Spravdi, koΩna verßyna hrafa K n , wo
[ centrom spruta, moΩe dlq inßyx sprutiv faktoryzaci] Φ buty lyße kince-
vog verßynog. Inßi Ω verßyny u sprutax iz Φ matymut\ stepeni 1 ta 2, a1tomu
moΩut\ maty u Φ til\ky druhyj z ukazanyx typiv.
Poznaçymo çerez A mnoΩynu verßyn perßoho typu faktoryzaci] Φ, a çe-
rez B — mnoΩynu verßyn druhoho typu i rozhlqnemo mnoΩynu ( A, B ) vsix re-
ber, wo z’[dnugt\ verßyny mnoΩyny A z verßynamy mnoΩyny B. Kil\kist\
takyx reber dorivng[ k
2
, i koΩne z nyx naleΩyt\ deqkomu sprutu z Φ. Z inßo-
ho boku, sered cyx reber moΩut\ buty lyße k reber, wo z’[dnugt\ centry
sprutiv z ]x kincevymy verßynamy (po odnomu rebru z koΩnoho spruta), ta rebra
— kinci wupalec\ sprutiv, us\oho ( s + 1 ) k reber. Ale Ω ( s + 1 ) k < k
2
dlq vsix
k > 2, i cej deficyt reber zumovlg[ supereçnist\ zi zroblenym prypuwennqm.
Teoremu dovedeno.
U vypadku n = 10 teoremu 2 dovedeno v ·3‚.
Naslidok. Ne isnu[ T -faktoryzacij dlq ( 12, s ) -sprutiv porqdku 12, u
qkyx s < 5.
Sered sprutiv porqdku 12 rivno 6 takyx, wo zadovol\nqgt\ umovy naslidku.
Ci spruty navedeno u tabl. 5.
Nazvemo verßynu x dereva T ekstremal\nog, qkwo ]] stepin\ dorivng[ 1
abo ∆ ( T ) . Vsi inßi verßyny dereva T nazyvatymemo neekstremal\nymy. Nexaj
r ( T ) — kil\kist\ reber u derevi T, qki z’[dnugt\ neekstremal\ni verßyny.
Teorema 3. Qkwo T — derevo porqdku n = 2k, ∆ ( T ) = k i r ( T ) < k −1
2
,
to T-faktoryzaci] nemoΩlyvi.
ISSN 1027-3190. Ukr. mat. Ωurn., 2006, t. 58, # 5
672 A. Q. PETRENGK
Tablycq 5
d N T
6 5 0 0 0 1 14
15
16
17
18
19
12 13 14 15 16 17 28 39 4A 5B 8C
28 39 4A 8B 9C
28 39 4A 8B BC
28 39 8A 9B AC
28 39 8A AB BC
78 89 9A AB BC
Dovedennq. Prypustymo, wo isnu[ T-faktoryzaciq hrafa K n . Poznaçymo
çerez B mnoΩynu tyx verßyn hrafa K n , qki ne [ maksymal\nymy v Ωodnij
z1komponent ci[] faktoryzaci]. Todi vsi neekstremal\ni verßyny komponent
naleΩat\ mnoΩyni B i, otΩe, ne menße niΩ k r ( T ) riznyx reber z’[dnugt\
verßyny z mnoΩyny B. Ale verßyny mnoΩyny B z’[dnugt\sq rivno
k −1
2
rebramy, otΩe, k r ( T ) ≤ k k( )−1
2
, zvidky r ( T ) ≤
k −1
2
, wo supereçyt\ umovi teo-
remy. Takym çynom, zroblene prypuwennq [ xybnym, i teoremu dovedeno.
Cq teorema vstanovlg[ neisnuvannq T-faktoryzacij dlq derev porqdku 12,
navedenyx u tabl. 6.
Tablycq 6
d N T
7 3 1 0 0 1 20
21
22
23
24
25
12 13 14 15 16 17 28 89 9A AB AC
28 89 9A 9B AC
28 89 8A 9B BC
28 89 8A 9B AC
28 29 8A AB BC
28 29 8A 9B AC
Poznaçymo çerez q ( T ) kil\kist\ reber dereva T, wo z’[dnugt\ ekstremal\-
ni verßyny c\oho dereva.
Teorema 4. Qkwo T — derevo porqdku n = 2k i pry c\omu ∆ ( T ) = k ta
q ( T ) < k − 1
2
, to T-faktoryzaci] nemoΩlyvi.
Dovedennq. Prypustymo protyleΩne, tobto pry vykonanni umov teoremy
isnu[ T-faktoryzaciq Φ. Poznaçymo çerez A mnoΩynu tyx verßyn hrafa K n ,
wo magt\ stepin\ ∆ ( T ) v odnij iz komponent T-faktoryzaci] Φ. KoΩne rebro,
wo z’[dnu[ verßyny z A, povynno z’[dnuvaty ekstremal\ni verßyny deqko] kom-
ponenty. Zahal\na kil\kist\ takyx reber u Φ dorivng[ k q ( T ), otΩe, k q ( T ) ≥
≥ k k( )− 1
2
, zvidky q ( T ) ≥ k − 1
2
, a ce supereçyt\ umovi.
Teoremu dovedeno.
Z ci[] teoremy vyplyva[ neisnuvannq T-faktoryzacij dlq derev porqdku 12,
vkazanyx u tabl. 7.
Zaznaçymo, wo dlq çastkovoho vypadku n = 14 teoremy 3 ta 4 sformul\ova-
no bez dovedennq u ·4‚.
Teorema 5. Derevo T, zobraΩene na rys. 1, ne dopuska[ T-faktoryzaci].
ISSN 1027-3190. Ukr. mat. Ωurn., 2006, t. 58, # 5
NEISNUVANNQ DEQKYX T-FAKTORYZACIJ PORQDKU 12 673
Rys. 1
Tablycq 7
d N T
6 5 0 0 0 1 26
27
28
12 13 14 15 16 17 28 39 4A 5B 6C
28 29 3A 4B 5C
28 39 4A 5B 8C
Dovedennq. Prypustymo protyleΩne, tobto dlq c\oho dereva isnu[ T-fak-
toryzaciq Φ. Ma[mo d ( T ) = ( 5, 6, 0, 0, 1, 0 ), i z tabl. 3 vyplyva[, wo sered
verßyn hrafa K12 [ 6 verßyn typu 6 (mnoΩynu takyx verßyn poznaçymo A ) ta
6 verßyn typu 1 (mnoΩyna B ). U mnoΩyni B zakinçugt\sq toçno 6 kincevyx
reber komponent. Tomu z 6 q ( T ) = 24 reber faktoryzaci] Φ, wo z’[dnugt\
verßyny stepenq 5 z kincevymy verßynamy komponent, ne menße niΩ 241–16 =
=118 reber leΩat\ u mnoΩyni A. Ale ce supereçyt\ tomu, wo verßyny mnoΩy-
ny A z’[dnugt\sq lyße 15 rebramy. OderΩana supereçnist\ dovodyt\ teoremu.
Teorema 6. Derevo T, zobraΩene na rys. 2, ne dopuska[ T-faktoryzaci].
Rys. 2
Dovedennq. Prypustymo protyleΩne, tobto isnu[ faktoryzaciq Φ z kom-
ponentamy, izomorfnymy derevu T. Qk i v poperednij teoremi, d = ( 5, 6, 0, 0, 1,
0 ), tomu vvedemo poznaçennq A ta B analohiçno. U mnoΩyni A leΩat\ toçno
6 verßyn, qki magt\ stepin\ 2 u komponentax. Tomu verßyny mnoΩyny A mo-
Ωut\ z’[dnuvatysq ne bil\ße niΩ 12 rebramy (z tyx, wo z’[dnugt\ u komponen-
tax maksymal\ni verßyny z verßynamy stepenq 2, ta tyx, wo z’[dnugt\ po dvi
verßyny stepenq 2). Ce supereçyt\ tomu, wo u mnoΩyni A leΩat\ toçno 15 re-
ber, i teoremu dovedeno.
Teorema 7. Dlq derev, zobraΩenyx na rys. 3, ne isnu[ T-faktoryzacij.
Rys. 3
ISSN 1027-3190. Ukr. mat. Ωurn., 2006, t. 58, # 5
674 A. Q. PETRENGK
Dovedennq. Nexaj T — odne z derev, zobraΩenyx na rys. 3. Prypustymo,
wo vsupereç tverdΩenng teoremy isnu[ T-faktoryzaciq Φ. Poznaçymo çerez A
mnoΩynu tyx verßyn hrafa K12 , qki [ verßynamy stepenq 5 u komponentax
faktoryzaci] Φ. MnoΩynu reber, wo z’[dnugt\ miΩ sobog verßyny z A, po-
znaçymo 〈 A 〉.
Todi, oçevydno, | A | = 6, | 〈 A 〉 | = 15. Z inßoho boku, d ( T ) = ( 5, 6, 0, 0, 1, 0 )
i, zhidno z tabl. 2, ma[mo β ( Φ ) = ( 6, 0, 0, 0, 0, 6, 0 ) , otΩe, vsi 6 verßyn v A
magt\ typ t 6 = ( 5, 1, 0, 0, 1 ). Sered reber, wo z’[dnugt\ ci verßyny, moΩut\
buty ti, wo z’[dnugt\ u komponentax maksymal\ni verßyny z kincevymy (takyx
reber u Φ rivno 6), ta ti, wo incydentni u komponentax verßynam stepenq 2.
Lehko zrozumity, wo qki b p verßyn druhoho vydu u derevi T ne vzqty, vony
z’[dnani miΩ sobog ne bil\ße niΩ p rebramy. Tomu 〈 A 〉 mistyt\ ne bil\ße niΩ
6 reber, wo z’[dnugt\ verßyny druhoho vydu. OtΩe, Φ pokryva[ ne bil\ße niΩ
12 reber z 〈 A 〉, a ne vsi 15 reber, wo supereçyt\ oznaçenng T-faktoryzaci]. Cq
supereçnist\ dovodyt\ teoremu.
6. Vysnovky ta zauvaΩennq. Na zaverßennq sformulg[mo osnovnyj re-
zul\tat statti u takomu vyhlqdi.
Teorema 8. Isnugt\ ne menße niΩ 32 takyx neizomorfnyx dopustymyx de-
reva porqdku 12, qki ne dopuskagt\ T-faktoryzacij.
Vidmitymo deqki osoblyvosti, qkymy vypadok n = 12 vyriznq[t\sq z-pomiΩ
doslidΩenyx vypadkiv n = 10 ta n = 14. Ce porivnqno velyka kil\kist\ derev,
dlq qkyx T-faktoryzaci] nemoΩlyvi. Mabut\, cq osoblyvist\ pov’qzana z vid-
sutnistg bicykliçnyx T-faktoryzacij, tomu slid çekaty podibnoho i dlq po-
dal\ßyx porqdkiv n = 2k ≡ 0 ( mod 4 ) .
U procesi provedenoho vywe doslidΩennq vyqvleno try rivni, na qkyx roz-
v’qzu[t\sq zadaça isnuvannq T-faktoryzacij: riven\ znaçen\ invarianta d de-
rev-komponent (teorema 1), riven\ typiv T-faktoryzacij (zadaça 1), indyvidual\-
nyj riven\ — riven\ konkretnoho dereva-komponenty (teoremy 5 – 7). We bil\ß
hlybokyj riven\ ma[ zadaça pereliku, z toçnistg do izomorfizmu, T-faktoryza-
cij dlq zadanoho dereva. Pryklady takyx perelikiv navedeno v ·7, 8‚.
1. Beineke L. W. Decomposition of complete graphs into forests // Magy. tud. akad. Mat. kut. int.
közl. – 1964. – # 9. – P. 589 – 594.
2. Huang C., Rosa A. Decomposition of complete graphs into trees // Ars Combinatoria. – 1978. –
# 5. – P. 23 – 63.
3. Petrenjuk A. J. On tree factorizations of K10 // J. Combin. Math. and Combin. Comput. – 2002. –
41. – P. 193 – 202.
4. Petrengk A. Q. Drevesn¥e faktoryzacyy poln¥x hrafov: suwestvovanye, postroenye, pe-
reçyslenye // Mat. 7 MeΩdunar. sem. „Dyskretnaq matematyka y ee pryloΩenyq” (Moskva,
29 qnv. – 2 fevr. 2001 h.). – M., 2001. – S. 261–130.
5. Petrengk A. Q. Pivobertovi derevni faktoryzaci] povnyx hrafiv // Ukr. mat. Ωurn. – 2001.
– 53, # 5. – S. 7101–1716.
6. Petrengk A. Q. Neobxidni umovy isnuvannq T-faktoryzacij // Dopov. NAN Ukra]ny. –
2002. – # 3. – S. 711–173.
7. Petrengk A. Q. Ekstremal\ni rozklady povnyx hrafiv: isnuvannq, perelik: dys. … d-ra
fiz.-mat. nauk. – Ky]v, 2002. – 266 s.
8. Petrenjuk A. J. Nonisomorphic double star factorizations of order 12 // Naukovi pr. akad. / Red.
R.1M. Makarov. – Kirovohrad: Vyd-vo DerΩ. l\ot. akad. Ukra]ny, 1999. – Vyp. 4, ç. 1. –
S.12121–1214.
OderΩano 09.11.2004
ISSN 1027-3190. Ukr. mat. Ωurn., 2006, t. 58, # 5
|
| id | umjimathkievua-article-3484 |
| institution | Ukrains’kyi Matematychnyi Zhurnal |
| keywords_txt_mv | keywords |
| language | Ukrainian English |
| last_indexed | 2026-03-24T02:43:23Z |
| publishDate | 2006 |
| publisher | Institute of Mathematics, NAS of Ukraine |
| record_format | ojs |
| resource_txt_mv | umjimathkievua/72/d5c440e129be99f7e8c94be10b51cb72.pdf |
| spelling | umjimathkievua-article-34842020-03-18T19:55:42Z Nonexistence of some T-factorizations of order 12 Неіснування деяких T-факторизацій порядку 12 Petrenyuk, A. Ya. Петренюк, А. Я. We investigate the Beineke problem of the existence of T-factorizations of complete graphs and prove several theorems on the existence of T-factorizations. Using these theorems, we establish the nonexistence of T-factorizations for 32 nonisomorphic admissible trees of order 12. Досліджується задача Л. Вайнеке про існування T-факторизацій повних графів. Доведено кілька теорем про існування T-факторизацій; з їх допомогою встановлено неіснування T-факторизацій для 32 неізоморфних допустимих дерев порядку 12. Institute of Mathematics, NAS of Ukraine 2006-05-25 Article Article application/pdf https://umj.imath.kiev.ua/index.php/umj/article/view/3484 Ukrains’kyi Matematychnyi Zhurnal; Vol. 58 No. 5 (2006); 666–674 Український математичний журнал; Том 58 № 5 (2006); 666–674 1027-3190 uk en https://umj.imath.kiev.ua/index.php/umj/article/view/3484/3705 https://umj.imath.kiev.ua/index.php/umj/article/view/3484/3706 Copyright (c) 2006 Petrenyuk A. Ya. |
| spellingShingle | Petrenyuk, A. Ya. Петренюк, А. Я. Nonexistence of some T-factorizations of order 12 |
| title | Nonexistence of some T-factorizations of order 12 |
| title_alt | Неіснування деяких T-факторизацій порядку 12 |
| title_full | Nonexistence of some T-factorizations of order 12 |
| title_fullStr | Nonexistence of some T-factorizations of order 12 |
| title_full_unstemmed | Nonexistence of some T-factorizations of order 12 |
| title_short | Nonexistence of some T-factorizations of order 12 |
| title_sort | nonexistence of some t-factorizations of order 12 |
| url | https://umj.imath.kiev.ua/index.php/umj/article/view/3484 |
| work_keys_str_mv | AT petrenyukaya nonexistenceofsometfactorizationsoforder12 AT petrenûkaâ nonexistenceofsometfactorizationsoforder12 AT petrenyukaya neísnuvannâdeâkihtfaktorizacíjporâdku12 AT petrenûkaâ neísnuvannâdeâkihtfaktorizacíjporâdku12 |