Корневое произведение

В теории графов корневое произведение графа G и корневого графа H определяется следующим образом: возьмём |V(G)| копий графа H и для каждой вершины $v_{i}$ графа G, отождествляем $v_{i}$ с корневой вершиной i-ой копии H.

Более формально. Предположим, что V(G) = {g₁, ..., g_n}, V(H) = {h₁, ..., h_m} и что корнем графа H является $h_{1}$ . Определим произведение

G\circ H:=(V,E)

где

V=\left\{(g_{i},h_{j}):1\leq i\leq n,1\leq j\leq m\right\}

E=\left\{((g_{i},h_{1}),(g_{k},h_{1})):(g_{i},g_{k})\in E(G)\right\}\cup \bigcup _{i=1}^{n}\left\{((g_{i},h_{j}),(g_{i},h_{k})):(h_{j},h_{k})\in E(H)\right\}

Если граф G является также корневым с корнем g₁, можно рассматривать произведение само как корневой граф с корнем (g₁, h₁). Корневое произведение является подграфом прямого произведения тех же самых двух графов.

Приложения

Корневое произведение особенно актуально для деревьев, поскольку корневое произведение двух деревьев снова будет деревом. Например, Кох и др. (1980) использовали корневые произведения для поиска грациозной нумерации для широкого семейства деревьев.

Если H — полный граф с двумя вершинами K₂, то для любого графа G корневое произведение графов G и H имеет число доминирования, равное ровно половине числа его вершин. Любой связный граф, в котором число доминирования равно половине вершин, получается таким образом, за исключением цикла с четырьмя вершинами. Эти графы можно использовать для генерации примеров, в которых для прямого произведения графов достигается граница из гипотезы Визинга, недоказанного неравенства между числом доминирования графов в различных произведениях графов^[1].

Примечания

↑ Fink, Jacobson, Kinch, Roberts, 1985.

Литература

C. D. Godsil, B. D. McKay. A new graph product and its spectrum // Bull. Austral. Math. Soc.. — 1978. — Т. 18, вып. 1. — С. 21–28. — doi:10.1017/S0004972700007760.
J. F. Fink, M. S. Jacobson, L. F. Kinch, J. Roberts. On graphs having domination number half their order // Period. Math. Hungar.. — 1985. — Т. 16, вып. 4. — С. 287–293. — doi:10.1007/BF01848079.
K. M. Koh, D. G. Rogers, T. Tan. Products of graceful trees // Discrete Mathematics. — 1980. — Т. 31, вып. 3. — С. 279–292. — doi:10.1016/0012-365X(80)90139-9.

Для улучшения этой статьи желательно:

Проверить качество перевода с иностранного языка.
Исправить статью согласно стилистическим правилам Википедии.

После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.

Read other articles:

List of recoilless rifles

This is a list of recoilless rifles (RCLs) intended to catalogue these lightweight infantry support weapons that allow the firing of a heavier projectile than would be practical with a recoiling artillery gun. Technically, only devices that use a rifled barrel are recoilless rifles. The smoothbore variants (those devoid of rifling) are termed recoilless guns. This distinction is often lost, and both are often called recoilless rifles. Normally used for anti-tank roles, the first effective sy...

Katedral Nova Gorica

Katedral Nova GoricaKon-Katedral Kristus Penyelamatbahasa Slovenia: Stolna cerkev Kristus OdrešenikLokasiNova GoricaNegara SloveniaDenominasiGereja Katolik RomaArsitekturStatusKon-katedralStatus fungsionalAktifAdministrasiKeuskupanKeuskupan Koper Katedral Kristus Sang Juru Selamat [1] (bahasa Slovenia: Stolna cerkev Kristus Odrešenik), disebut juga Katedral Nova Gorica, adalah sebuah gereja kon-katedral Katolik yang terletak di Nova Gorica, sebuah kota di negara Eropa, ...

Harjit Sajjan

Artikel ini perlu diwikifikasi agar memenuhi standar kualitas Wikipedia. Anda dapat memberikan bantuan berupa penambahan pranala dalam, atau dengan merapikan tata letak dari artikel ini. Untuk keterangan lebih lanjut, klik [tampil] di bagian kanan. Mengganti markah HTML dengan markah wiki bila dimungkinkan. Tambahkan pranala wiki. Bila dirasa perlu, buatlah pautan ke artikel wiki lainnya dengan cara menambahkan [[ dan ]] pada kata yang bersangkutan (lihat WP:LINK untuk keterangan lebih lanjut...

List of 500cc/MotoGP race winners

Fédération Internationalede MotocyclismeGrand Prix motorcycle racing Current season summary 2024 MotoGP World Championship 2024 Moto2 World Championship 2024 Moto3 World Championship 2024 MotoE World Championship Related MotoE Lists Riders Champions Race winners 500cc/MotoGP race winners MotoGP sprint race winners 500cc/MotoGP polesitters 500cc/MotoGP fastest laps Records 500cc/MotoGP Records Constructors Champions 500cc/MotoGP race winners Teams' Champions Grands Prix Circuits Points scor...

EXOR

EXORJenisSocietà per azioni (Perusahaan induk)Kode emitenBIT: EXOIndustriPerusahaan investasiDidirikan27 July 1927KantorpusatItaliaWilayah operasiSeluruh duniaTokohkunciJohn ElkannPendapatan$143,7 miliarTotal aset$170,7 miliarKaryawan318,562Situs webhttp://www.exor.com/ EXOR adalah sebuah perusahaan asal Italia yang bergerak di sektor finansial.[1] Fokus utama EXOR adalah industri jasa investasi.[1] Pada tahun 2014, EXOR mendapatkan penjualan sebesar AS$143,7 miliar deng...

Nexus International University

Private university in Uganda Nexus International University (NIU)TypePrivateEstablishedJanuary 1, 2012; 12 years ago (2012-01-01)Vice-ChancellorProfessor Magnus Amajirionwu[1]Location5158 Kayongo Road, Muyenga, Kampala, Uganda00°18′03″N 32°36′23″E / 0.30083°N 32.60639°E / 0.30083; 32.60639CampusUrbanWebsiteHomepageLocation in Kampala Nexus International University (NIU), formerly Virtual University of Uganda (VUU) is a private univ...

Public Investment Fund

Public Investment FundDidirikan17 Agustus 1971; 52 tahun lalu (1971-08-17)PendiriFaisal dari Arab SaudiKantorpusatRiyadh, Arab SaudiTokohkunciMohammad bin Salman (Ketua) Yasir Al-Rumayyan (Gubernur)AUM$500 miliar[1]Situs webwww.pif.gov.sa Public Investment Fund (PIF; Arab: صندوق الإستثمارات العامةcode: ar is deprecated ) adalah yayasan kekayaan kedaulatan Arab Saudi. Yayasan tersebut adalah salah satu yayasan kekayaan kedaulatan terbesar di dunia dengan tota...

Liga Leumit 1963-1964

Liga Leumit 1963-1964 Competizione Liga Leumit Sport Calcio Edizione 24ª Organizzatore IFA Date dal 12 ottobre 1963all'11 luglio 1964 Luogo Israele Partecipanti 15 Formula 1 girone all'italiana Risultati Vincitore Hapoel Ramat Gan(1º titolo) Retrocessioni Hapoel Lod Statistiche Miglior marcatore Israel Ashkenazi (21) Incontri disputati 210 Gol segnati 589 (2,8 per incontro) Cronologia della competizione 1962-1963 1964-1965 Manuale La Liga Leumit 1963-1964 è stata la 24...

David Frawley

David Frawley (Vamadeva Shastri)David Frawley pada tahun 2007Lahir21 September 1950 (umur 73)Wisconsin, Amerika SerikatKebangsaanAmerika SerikatPekerjaanWedakarya, Guru Ayurweda, astrolog Weda, penulisSuami/istriYogini Shambhavi ChopraSitus webwww.vedanet.com David Frawley (Sanskerta: वामदेव शास्त्री, IAST: Vāmadeva Śāstrī; lahir 21 September 1950), adalah seorang guru Hindu(akarya) Amerika Serikat dan aktivis Hindutva.[a][2] Ia menulis se...

Flat-headed kusimanse

Species of mongoose from West Africa Flat-headed kusimanse Conservation status Least Concern (IUCN 3.1)[1] Scientific classification Domain: Eukaryota Kingdom: Animalia Phylum: Chordata Class: Mammalia Order: Carnivora Suborder: Feliformia Family: Herpestidae Genus: Crossarchus Species: C. platycephalus Binomial name Crossarchus platycephalusGoldman, 1984 Flat-headed kusimanse range The flat-headed kusimanse (Crossarchus platycephalus) is a mongoose species endemic to West ...

Concours Eurovision de la chanson 1990

Concours Eurovision de la chanson 1990 Dates Finale 5 mai 1990 Retransmission Lieu Koncertna dvorana Vatroslav LisinskiZagreb, Yougoslavie Présentateur(s) Oliver Mlakar Helga Vlahović Directeur musical Igor Kuljerić Superviseur exécutif Frank Naef Télédiffuseur hôte Jugoslovenska Radio-Televizija (JRT) Ouverture Zagreb : ville de musique, film de Nenad Puhovski Entracte La Yougoslavie change, film de Ivo Laurenčić Participants Nombre de participants 22 Débuts Aucun Retour Aucu...

Jay-Jay Okocha

Biografi ini memerlukan lebih banyak catatan kaki untuk pemastian. Bantulah untuk menambahkan referensi atau sumber tepercaya. Materi kontroversial atau trivial yang sumbernya tidak memadai atau tidak bisa dipercaya harus segera dihapus, khususnya jika berpotensi memfitnah.Cari sumber: Jay-Jay Okocha – berita · surat kabar · buku · cendekiawan · JSTOR (Agustus 2023) (Pelajari cara dan kapan saatnya untuk menghapus pesan templat ini) Jay-Jay Okocha Muha...

American Civil War prison camps

Lists of prisoner of war camps A Union Army soldier barely alive in Georgia on his release in 1865. Both Confederate and Union prisoners of war suffered great hardships during their captivity. Between 1861 and 1865, American Civil War prison camps were operated by the Union and the Confederacy to detain over 400,000 captured soldiers. From the start of the Civil War through to 1863 a parole exchange system saw most prisoners of war swapped relatively quickly. However, from 1863 this broke dow...

1919 Mississippi gubernatorial election

Election for the governorship of the U.S. state of Mississippi 1919 Mississippi gubernatorial election ← 1915 November 4, 1919 1923 → Nominee Lee M. Russell J. T. Lester Party Democratic Socialist Popular vote 39,241 1,231 Percentage 96.96% 3.04% Governor before election Theodore G. Bilbo Democratic Elected Governor Lee M. Russell Democratic Elections in Mississippi Federal government U.S. President 1820 1824 1828 1832 1836 1840 1844 1848 1852 1856 1860 1872 ...

Media coverage of the assassination of John F. Kennedy

This article is part of a series aboutJohn F. Kennedy Military service in WWII Electoral history Why England Slept Profiles in Courage A Nation of Immigrants Family 35th President of the United States Presidency timeline Transition Inauguration Tenure Executive actions New Frontier Foreign policy Doctrine A Strategy of Peace Bay of Pigs Cuban Missile Crisis Civil Rights Address Partial Nuclear Test Ban Treaty Clean Air Peace Corps We choose to go to the Moon Space programs Mercury Gemini Apo...

T (New York City Subway service)

Future New York City Subway service New York City Subway serviceSecond Avenue LocalNorthern endHarlem–125th Street (Planned)Southern endHanover Square (Planned)Stations16Started serviceJune 24, 1916; 107 years ago (1916-06-24) (West End service)DiscontinuedNovember 26, 1967; 56 years ago (1967-11-26) (West End through service)July 1, 1968; 55 years ago (1968-07-01) (West End shuttle) Route map Legend Q T...

No. 100 Squadron RAF

Defunct flying squadron of the Royal Air Force No. 100 Squadron RAFSquadron badgeActive1917–1918 (RFC)1918–19421942–19591962–19681972–2022Disbanded31 March 2022Country United KingdomBranch Royal Air ForceTypeFlying squadronMotto(s)Sarang tebuan jangan dijolok(Malay for 'Never stir up a hornet's nest')[1]InsigniaSquadron badge heraldryIn front of two bones in saltire, a skull. The badge was the official version of a motif used by the squadron on the Western Front in 1...

Filipp Golikov

Filipp Ivanovich GolikovNama asliФилипп Иванович ГоликовLahirJuly 16 [K.J.: July 29] 1900Borisova, Kegubernuran Perm, Kekaisaran Rusia(sekarang Distrik Kataysky, Oblast Kurgan), RusiaMeninggal29 Juli 1980(1980-07-29) (umur 80)Moskwa, Republik Sosialis Federatif Soviet Rusia, Uni SovietPengabdianUni SovietDinas/cabangAngkatan Darat Uni Soviet, Direktorat Intelijensi UtamaLama dinas1918–1980PangkatMarsekal Uni Soviet (1961) Filipp Ivanovich Golikov (bahasa Rusia...

Scantic River

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Scantic River – news · newspapers · books · scholar · JSTOR (April 2011) (Learn how and when to remove this message) River in Massachusetts and Connecticut, United States The lower Scantic River and environs, depicted on an 1892 topographic map. In Hampden, Mas...

Roy E. Disney

Roy E. DisneyDisney pada tanggal 11 Desember 2007LahirRoy Edward Disney(1930-01-10)10 Januari 1930Los Angeles, California, ASMeninggal16 Desember 2009(2009-12-16) (umur 79)Newport Beach, California, ASPekerjaanEksekutif film Eksekutif bisnisTahun aktif1954–2009Suami/istriPatricia Ann Dailey (1955–2007)Leslie DeMeuse-Disney (2008–2009) Roy Edward Disney, KCSG (10 Januari 1930 – 16 Desember 2009)[1] adalah pejabat eksekutif senior The Walt Disney Company...

Pertempuran Civitate

/profillengkap.com/index.php/article/Hyderabad Metro

/profillengkap.com/index.php/article/1998–99 Primera Divisió

Maria Anna Mozart

Llanstephan, Powys

Northridge Blind Thrust Fault

Tegal Parang, Mampang Prapatan, Jakarta Selatan

Best management practice for water pollution