Nordhaus-Gaddum-Type Relations Over Invariants of a Graph and Its ?-Complement

Abstract

Let $G$ be a graph. The $\delta$-complement of $G$, denoted by $G_{\delta}$, was defined by Pai et al. (2022) to be a variation of a graph complement where two vertices are adjacent in $G_\delta$ if and only if they are of the same degree but not adjacent in $G$ or they are of different degrees but adjacent in $G$.We provide the sum and the product bounds, in the spirit of Nordhaus and Gaddum (1956) over several invariants of a graph and its $\delta$-complement: minimum degrees, maximum degrees, girths, diameters, radii, domination numbers, vertex connectivities, and edge connectivities.We also use Sagemath (2022) to compute the results on the graphs of order at most 10.

??? $G$ ???????? ??????????????? $\delta$ ???????????? $G_{\delta}$ ???????? Pai ?????? (2022) ???????????????????????????????????????????????????? ? ???????????????? $G_{\delta}$ ????????????????????????????????????????????????????????????? $G$ ??????????????????????????????????????????????????? $G$????????????????????????????????????????????????? Nordhaus ??? Gaddum (1956) ???????????????????????????? ? ????????????????????????? $\delta$-complement ???????????????????????? ?????????????? ????????? ??????????? ????? ????????? ????????????????????????? ????????????????????????????????????????????? Sagemath (2022) ?????????????????????????????????????????????? 10 ???