Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
A Note on Alon–Tarsi Shortest Cycle Cover Conjecture
View through CrossRef
ABSTRACT
The shortest cycle cover conjecture (SCC conjecture), proposed by Alon and Tarsi, asserts that every bridgeless cubic graph has a cycle cover with a total length at most . Tarsi further proposed a related conjecture, the conjecture, which states that every bridgeless cubic graph has a 3‐cycle cover with a total length at most . In this paper, we prove that every cyclically odd‐‐edge‐connected cubic graph has a 3‐cycle cover with a total length at most . Consequently, the SCC conjecture and the conjecture are verified in this paper for cubic graphs with cyclic odd‐edge‐connectivity at least 29 and 17, respectively. Additionally, for cubic graphs that satisfies Kaiser–Raspaud conjecture (i.e., every bridgeless cubic graph has two perfect matchings and and a parity subgraph , such that ), the SCC conjecture and the conjecture are verified for graphs with girth at least 20 and 10, respectively.
Title: A Note on Alon–Tarsi Shortest Cycle Cover Conjecture
Description:
ABSTRACT
The shortest cycle cover conjecture (SCC conjecture), proposed by Alon and Tarsi, asserts that every bridgeless cubic graph has a cycle cover with a total length at most .
Tarsi further proposed a related conjecture, the conjecture, which states that every bridgeless cubic graph has a 3‐cycle cover with a total length at most .
In this paper, we prove that every cyclically odd‐‐edge‐connected cubic graph has a 3‐cycle cover with a total length at most .
Consequently, the SCC conjecture and the conjecture are verified in this paper for cubic graphs with cyclic odd‐edge‐connectivity at least 29 and 17, respectively.
Additionally, for cubic graphs that satisfies Kaiser–Raspaud conjecture (i.
e.
, every bridgeless cubic graph has two perfect matchings and and a parity subgraph , such that ), the SCC conjecture and the conjecture are verified for graphs with girth at least 20 and 10, respectively.
Related Results
Ary Scheffer, een Nederlandse Fransman
Ary Scheffer, een Nederlandse Fransman
AbstractAry Scheffer (1795-1858) is so generally included in the French School (Note 2)- unsurprisingly, since his career was confined almost entirely to Paris - that the fact that...
Pieter Saenredam: zijn boekenbezit en zijn relatie met de landmeter Pieter Wils
Pieter Saenredam: zijn boekenbezit en zijn relatie met de landmeter Pieter Wils
AbstractAn earlier article on Saenredam's construction drawings (Note, 1 ) left open the question of how he obtained his knowledge of perspective. His teacher Frans de Grebber (Not...
Borel Conjecture, dual Borel Conjecture, and other variants of the Borel Conjecture
Borel Conjecture, dual Borel Conjecture, and other variants of the Borel Conjecture
This survey article is about the Borel Conjecture and several variants (which are inspired by the Galvin-Mycielski-Solovay characterization of strong measure zero) such as the dual...
Rosenfeld’s conjecture
Rosenfeld’s conjecture
Conjecture de rosenfeld
Ma thèse de Doctorat est basée sur un sujet très intéressant en Théorie de Graphe : Le tournoi.En 1934, Rédei a prouvé que tout tournoi cont...
Een serie tekeningen van Johannes Stradanus met scènes uit het leven van de Heilige Giovanni Gualberto
Een serie tekeningen van Johannes Stradanus met scènes uit het leven van de Heilige Giovanni Gualberto
AbstractAmong the extensive collection of pen sketches by Johannes Stradanus (Bruges 1523-Florence 1605) in the Cooper-Hewitt Museum of Design and the Pierpont Morgan Library in Ne...
The Alon-Tarsi number of planar graphs without some forbidden configurations
The Alon-Tarsi number of planar graphs without some forbidden configurations
The Alon-Tarsi number of a graph G AT(G) defined as the smallest integer k admitting an Alon-Tarsi orientation with maximum out-degree at most k-1, satisfies the fundamental inequ...
Cover Crop Response to Late‐Season Planting and Nitrogen Application
Cover Crop Response to Late‐Season Planting and Nitrogen Application
Cover crops aid in reducing precipitation runoff, soil erosion, and N losses in highly sloped, mountainous regions. Corn (Zea mays L.) producers in states with late spring warmup a...
The Galois Brumer–Stark conjecture for SL2(????3)-extensions
The Galois Brumer–Stark conjecture for SL2(????3)-extensions
In a previous work, we stated a conjecture, called the Galois Brumer–Stark conjecture, that generalizes the (abelian) Brumer–Stark conjecture to Galois extensions. We also proved t...