A Note on Signed k-Submatching in Graphs

Abstract

Let $G$ be a graph of order $n$. For every $v\in V(G)$, let $E_G(v)$ denote the set of all edges incident with $v$. A signed $k$-submatching of $G$ is a function $f:E(G)⟶\{-1,1\}$, satisfying $f(E_G(v))\le 1$ for at least $k$ vertices, where $f(S)={\sum }_{e\in S}f(e)$, for each $S\subseteq E(G)$. The maximum of the value of $f(E(G))$, taken over all signed $k$-submatching $f$ of $G$, is called the signed $k$-submatching number and is denoted by ${\beta }_S^k(G)$. In this paper, we prove that for every graph $G$ of order $n$ and for any positive integer $k\le n$, ${\beta }_S^k(G)\ge n-k-\omega (G)$, where $w(G)$ is the number of components of $G$. This settles a conjecture proposed by Wang. Also, we present a formula for the computation of ${\beta }_S^n(G)$.

4 pages