文献类型：期刊文献

英文题名：Nordhaus-Gaddum type inequality for the integer k-matching number of a graph?

作者：Chen, Qian-Qian[1];Guo, Ji-Ming[1]

机构：[1]East China Univ Sci & Technol, Sch Math, Shanghai, Peoples R China

年份：2023

卷号：340

起止页码：21

外文期刊名：DISCRETE APPLIED MATHEMATICS

收录：;EI(收录号：20232914418926);WOS:【SCI-EXPANDED(收录号:WOS:001043839100001)】；

基金：This work is supported by NSFC (No. 12171154)

语种：英文

外文关键词：Graph; Nordhaus-Gaddum type inequality; Integer k-matching number

摘要：An integer k-matching of a graph G is a function h : E(G)-> {0, 1, ... , k} such that Sigma(e epsilon Gamma)(v)h(e) <= k for any v epsilon V(G), where & UGamma;(v) is the set of edges incident to v. The integer k-matching number of G, denoted by mk(G), is the maximum number of e & ISIN;E(G)h(e) over all integer k-matching h of G. In this paper, we establish the following lower bounds on the sum of the integer k-matching number of a graph G and its complement by using Gallai-Edmonds Structure Theorem: (1) mk(G) + mk(G) & GE; L nk2 RIGHT FLOOR forn & GE; 2; (2) if G and G are non-empty, then for n & GE; 25, mk(G) + mk(G) & GE; L nk+k (3) if G and G have no isolated vertices, then for n & GE; 25, mk(G) + mk(G) & GE; L nk2 RIGHT FLOOR + 2k . Furthermore, all extremal graphs attaining the lower bounds are also characterized. & COPY; 2023 Elsevier B.V. All rights reserved.