Two-block paths in oriented graphs of large semidegree
| Title: | Two-block paths in oriented graphs of large semidegree |
|---|---|
| Authors: | Penev, Irena, Taruni, S, Thomassé, Stéphan, Trujillo-Negrete, Ana, Tyomkyn, Mykhaylo |
| Publication Year: | 2025 |
| Collection: | Mathematics |
| Subject Terms: | Mathematics - Combinatorics |
| More Details: | We study the existence of oriented paths with two blocks in oriented graphs under semidegree conditions. A block of an oriented path is a maximal directed subpath. Given positive integers $k$ and $\ell$ with $k/2\le \ell < k$, we establish a semidegree function that guarantees the containment of every oriented path with two blocks of sizes $\ell$ and $k-\ell$. As a corollary, we show that every oriented graph with all in- and out-degrees at least $3k/4$ contains every two-block path with $k$ arcs. Our results extend previous work on Stein's conjecture and related problems concerning oriented paths. |
| Document Type: | Working Paper |
| Access URL: | http://arxiv.org/abs/2503.23191 |
| Accession Number: | edsarx.2503.23191 |
| Database: | arXiv |
| FullText | Text: Availability: 0 CustomLinks: – Url: http://arxiv.org/abs/2503.23191 Name: EDS - Arxiv Category: fullText Text: View this record from Arxiv MouseOverText: View this record from Arxiv – Url: https://resolver.ebsco.com/c/xy5jbn/result?sid=EBSCO:edsarx&genre=article&issn=&ISBN=&volume=&issue=&date=20250329&spage=&pages=&title=Two-block paths in oriented graphs of large semidegree&atitle=Two-block%20paths%20in%20oriented%20graphs%20of%20large%20semidegree&aulast=Penev%2C%20Irena&id=DOI: Name: Full Text Finder (for New FTF UI) (s8985755) Category: fullText Text: Find It @ SCU Libraries MouseOverText: Find It @ SCU Libraries |
|---|---|
| Header | DbId: edsarx DbLabel: arXiv An: edsarx.2503.23191 RelevancyScore: 1147 AccessLevel: 3 PubType: Report PubTypeId: report PreciseRelevancyScore: 1146.580078125 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Two-block paths in oriented graphs of large semidegree – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Penev%2C+Irena%22">Penev, Irena</searchLink><br /><searchLink fieldCode="AR" term="%22Taruni%2C+S%22">Taruni, S</searchLink><br /><searchLink fieldCode="AR" term="%22Thomassé%2C+Stéphan%22">Thomassé, Stéphan</searchLink><br /><searchLink fieldCode="AR" term="%22Trujillo-Negrete%2C+Ana%22">Trujillo-Negrete, Ana</searchLink><br /><searchLink fieldCode="AR" term="%22Tyomkyn%2C+Mykhaylo%22">Tyomkyn, Mykhaylo</searchLink> – Name: DatePubCY Label: Publication Year Group: Date Data: 2025 – Name: Subset Label: Collection Group: HoldingsInfo Data: Mathematics – Name: Subject Label: Subject Terms Group: Su Data: <searchLink fieldCode="DE" term="%22Mathematics+-+Combinatorics%22">Mathematics - Combinatorics</searchLink> – Name: Abstract Label: Description Group: Ab Data: We study the existence of oriented paths with two blocks in oriented graphs under semidegree conditions. A block of an oriented path is a maximal directed subpath. Given positive integers $k$ and $\ell$ with $k/2\le \ell < k$, we establish a semidegree function that guarantees the containment of every oriented path with two blocks of sizes $\ell$ and $k-\ell$. As a corollary, we show that every oriented graph with all in- and out-degrees at least $3k/4$ contains every two-block path with $k$ arcs. Our results extend previous work on Stein's conjecture and related problems concerning oriented paths. – Name: TypeDocument Label: Document Type Group: TypDoc Data: Working Paper – Name: URL Label: Access URL Group: URL Data: <link linkTarget="URL" linkTerm="http://arxiv.org/abs/2503.23191" linkWindow="_blank">http://arxiv.org/abs/2503.23191</link> – Name: AN Label: Accession Number Group: ID Data: edsarx.2503.23191 |
| PLink | https://login.libproxy.scu.edu/login?url=https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&scope=site&db=edsarx&AN=edsarx.2503.23191 |
| RecordInfo | BibRecord: BibEntity: Subjects: – SubjectFull: Mathematics - Combinatorics Type: general Titles: – TitleFull: Two-block paths in oriented graphs of large semidegree Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Penev, Irena – PersonEntity: Name: NameFull: Taruni, S – PersonEntity: Name: NameFull: Thomassé, Stéphan – PersonEntity: Name: NameFull: Trujillo-Negrete, Ana – PersonEntity: Name: NameFull: Tyomkyn, Mykhaylo IsPartOfRelationships: – BibEntity: Dates: – D: 29 M: 03 Type: published Y: 2025 |
| ResultId | 1 |