A note on maximum fractional matchings of graphs

Tianlong Ma (), Eddie Cheng (), Yaping Mao () and Xu Wang ()
Additional contact information
Tianlong Ma: Xiamen University
Eddie Cheng: Oakland University
Yaping Mao: Qinghai Normal University
Xu Wang: Qinghai Normal University

Journal of Combinatorial Optimization, 2022, vol. 43, issue 1, No 13, 253-264

Abstract: Abstract A fractional matching of a graph G is a function f giving each edge a number in [0, 1] so that $$\sum _{e\in \Gamma _G (v)} f(e)\le 1 $$ ∑ e ∈ Γ G ( v ) f ( e ) ≤ 1 for each $$v \in V(G)$$ v ∈ V ( G ) , where $$\Gamma _G (v)$$ Γ G ( v ) is the set of edges incident to v in G. The fractional matching number of G, denoted by $$\mu _f(G)$$ μ f ( G ) , is the maximum of $$\sum _{e\in E(G)} f(e)$$ ∑ e ∈ E ( G ) f ( e ) over all fractional matchings f. A fractional matching f of G is called a maximum fractional matching if $$\sum _{e\in E(G)} f(e)=\mu _f(G)$$ ∑ e ∈ E ( G ) f ( e ) = μ f ( G ) . In this paper, as a supplement of known results in Liu et al. (J Comb Optim 40:59–68, 2020), we further study the maximum fractional matching, and give some sufficient and necessary conditions to characterize the maximum fractional matching. Furthermore, as applications, the sharp lower bounds of the fractional matching number for Cartesian product, strong product, lexicographic product and direct product are obtained.

Keywords: Matching; Gallai–Edmonds decomposition; Maximum fractional matching; Fractional matching number; Cartesian product; Strong product; Lexicographic product; Direct product; 05C76; 05C70; 05C72 (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-021-00766-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jcomop:v:43:y:2022:i:1:d:10.1007_s10878-021-00766-6

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-021-00766-6

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().