During the last five decades, many different secondary constructions of bent functions were proposed in the literature. Nevertheless, apart from a few works, the question about the class inclusion of ...bent functions generated using these methods is rarely addressed. Especially, if such a “new” family belongs to the completed Maiorana–McFarland (
M
M
#
) class then there is no proper contribution to the theory of bent functions. In this article, we provide some fundamental results related to the inclusion in
M
M
#
and eventually we obtain many infinite families of bent functions that are provably outside
M
M
#
. The fact that a bent function
f
is in/outside
M
M
#
if and only if its dual is in/outside
M
M
#
is employed in the so-called 4-decomposition of a bent function on
F
2
n
, which was originally considered by Canteaut and Charpin (IEEE Trans Inf Theory 49(8):2004–2019, 2003) in terms of the second-order derivatives and later reformulated in (Hodžić et al. in IEEE Trans Inf Theory 65(11):7554–7565, 2019) in terms of the duals of its restrictions to the cosets of an
(
n
-
2
)
-dimensional subspace
V
. For each of the three possible cases of this 4-decomposition of a bent function (all four restrictions being bent, semi-bent, or 5-valued spectra functions), we provide generic methods for designing bent functions provably outside
M
M
#
. For instance, for the elementary case of defining a bent function
h
(
x
,
y
1
,
y
2
)
=
f
(
x
)
⊕
y
1
y
2
on
F
2
n
+
2
using a bent function
f
on
F
2
n
, we show that
h
is outside
M
M
#
if and only if
f
is outside
M
M
#
. This approach is then generalized to the case when two bent functions are used. More precisely, the concatenation
f
1
|
|
f
1
|
|
f
2
|
|
(
1
⊕
f
2
)
also gives bent functions outside
M
M
#
if
f
1
or
f
2
is outside
M
M
#
. The cases when the four restrictions of a bent function are semi-bent or 5-valued spectra functions are also considered and several design methods of constructing infinite families of bent functions outside
M
M
#
are provided.
Full text
Available for:
EMUNI, FIS, FZAB, GEOZS, GIS, IJS, IMTLJ, KILJ, KISLJ, MFDPS, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, SBMB, SBNM, UKNU, UL, UM, UPUK, VKSCE, ZAGLJ
Let G denote a multigraph with edge set E(G), let µ(G) denote the maximum edge multiplicity in G, and let Pk denote the path on k vertices. Heinrich et al.(1999) showed that P4 decomposes a connected ...4-regular graph G if and only if |E(G)| is divisible by 3. We show that P4 decomposes a connected 4-regular multigraph G with µ(G) ≤2 if and only if no 3 vertices of G induce more than 4 edges and |E(G)| is divisible by 3. Oksimets (2003) proved that for all integers k ≥3, P4 decomposes a connected 2k-regular graph G if and only if |E(G)| is divisible by 3. We prove that for all integers k ≥2, the problem of determining if P4 decomposes a (2k + 1)-regular graph is NP-Complete. El-Zanati et al.(2014) showed that for all integers k ≥1, every 6k-regular multigraph with µ(G) ≤2k has a P4-decomposition. We show that unless P = NP, this result is best possible with respect to µ(G) by proving that for all integers k ≥3 the problem of determining if P4 decomposes a 2k-regular multigraph with µ(G) ≤⌊2k / 3 ⌋+ 1 is NP-Complete.
Full text
Available for:
DOBA, IZUM, KILJ, NUK, PILJ, PNG, SAZU, UILJ, UKNU, UL, UM, UPUK
PDF