Graphs whose the maximum size of an odd subgraph equal to ⌊n2⌋

Si-Ao Xu and Baoyindureng Wu

Applied Mathematics and Computation, 2025, vol. 494, issue C

Abstract: A graph is said to be odd if the degrees of all vertices are odd. A subgraph F of X is called an odd factor of X if F is odd and V(F)=V(X). Let fo′(X)=max⁡{|S|:S⊆E(X),X[S] is odd} and fo″(X)=max⁡{|S|:S⊆E(X),X[S] is an odd factor of X}. In 2001, Scott established that every connected graph X of even order admits a vertex partition A1,…,As such that the induced graph X[Ai] is odd for i∈{1,…,s}. It implies that for a graph of order n, fo′(X)≥⌊n2⌋, and fo″(X)≥n2 if n is even. In this paper, first we characterize all trees T with the property that T−v has a perfect matching for any leaf v. Thereby, we comprehensively characterize all connected graphs that attain the tight lower bounds for fo′(X) and fo″(X) respectively.

Keywords: Odd factors; Odd subgraphs; Perfect matchings (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300325000244
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:494:y:2025:i:c:s0096300325000244

DOI: 10.1016/j.amc.2025.129297

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().