A set <inline-formula> <tex-math notation="LaTeX">$S\subseteq V(G)$ </tex-math></inline-formula> is called a <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-total dominating set of a graph <inline-formula> <tex-math notation="LaTeX">$G$ </tex-math></inline-formula> if every vertex of <inline-formula> <tex-math notation="LaTeX">$G$ </tex-math></inline-formula> lies within distance at most <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> of some other vertex in <inline-formula> <tex-math notation="LaTeX">$S$ </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">$k\ge 1$ </tex-math></inline-formula>. The minimum cardinality of such a set is called the <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-total domination number of <inline-formula> <tex-math notation="LaTeX">$G$ </tex-math></inline-formula>, denoted by <inline-formula> <tex-math notation="LaTeX">$\gamma _{t,k}(G)$ </tex-math></inline-formula>. In this paper, we investigate <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-total domination from a coverage-based perspective. We establish a new lower bound for <inline-formula> <tex-math notation="LaTeX">$\gamma _{t,k}(G)$ </tex-math></inline-formula> in terms of the diameter of <inline-formula> <tex-math notation="LaTeX">$G$ </tex-math></inline-formula>. To analyze neighborhood coverage in <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-total domination, we extend the concepts of shadow and share to <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-neighborhoods and introduce the neighborhood coverage number. We also extend the concept of redundant domination to the setting of <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-neighborhoods. Together, these concepts quantify both the coverage provided by <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-neighborhoods and the overlap among them. These concepts yield new insights into the structure of <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-total dominating sets and are applied to obtain results for circulant graphs. We show that the shadow graph operation preserves the <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-total domination number; that is, <inline-formula> <tex-math notation="LaTeX">$\gamma _{t,k}(D_{2}(G))=\gamma _{t,k}(G)$ </tex-math></inline-formula> for every graph <inline-formula> <tex-math notation="LaTeX">$G$ </tex-math></inline-formula>. For strong product graphs, we establish general upper bounds and prove that <inline-formula> <tex-math notation="LaTeX">$\gamma _{t,k}(H\boxtimes H')=\gamma _{t,k}(H)$ </tex-math></inline-formula> whenever <inline-formula> <tex-math notation="LaTeX">$r(H')\le k$ </tex-math></inline-formula>. As a consequence, we obtain exact values of the <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-total domination number for several classes of shadow and strong product graphs, including shadow graphs of paths and cycles, and strong products of paths and cycles.
Let <inline-formula> <tex-math notation="LaTeX">$\mathcal {C}_{(q,q^{m}+1,3,h)}$ </tex-math></inline-formula> denote the antiprimitive BCH code with designed distance 3. For any <inline-formula> <tex-math notation="LaTeX">$q$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$m$ </tex-math></inline-formula>, we demonstrate that the minimum distance <inline-formula> <tex-math notation="LaTeX">$d$ </tex-math></inline-formula> of <inline-formula> <tex-math notation="LaTeX">$\mathcal {C}_{(q,q^{m}+1,3,h)}$ </tex-math></inline-formula> equals 3 if and only if <inline-formula> <tex-math notation="LaTeX">$\gcd (2h+1,q+1,q^{m}+1)\ne 1$ </tex-math></inline-formula>. For odd <inline-formula> <tex-math notation="LaTeX">$q$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$m$ </tex-math></inline-formula>, we show that <inline-formula> <tex-math notation="LaTeX">$d=4$ </tex-math></inline-formula> if and only if <inline-formula> <tex-math notation="LaTeX">$\gcd (2h+1,q+1)=1$ </tex-math></inline-formula>, thereby fully characterizing the minimum distance in this case. For even <inline-formula> <tex-math notation="LaTeX">$q$ </tex-math></inline-formula> or even <inline-formula> <tex-math notation="LaTeX">$m$ </tex-math></inline-formula>, we establish some sufficient conditions for <inline-formula> <tex-math notation="LaTeX">$d=4$ </tex-math></inline-formula> or <inline-formula> <tex-math notation="LaTeX">$d=5$ </tex-math></inline-formula>. Additionally, we investigate the parameters of <inline-formula> <tex-math notation="LaTeX">$\mathcal {C}_{(q,q^{m}+1,3,h)}$ </tex-math></inline-formula> for certain <inline-formula> <tex-math notation="LaTeX">$h$ </tex-math></inline-formula>, and present two infinite families of distance-optimal codes as well as several linear codes with the best known parameters.
Haojie Xu, Xia Wu, Wei Lu et al.· IEEE Transactions on Informa...· 0 citations
Let M and N be closed subspaces of a Hilbert space <inline-formula> <tex-math notation="LaTeX">$\mathbb {H}$ </tex-math></inline-formula>, and let <inline-formula> <tex-math notation="LaTeX">$\Pi _{M}$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$\Pi _{N}$ </tex-math></inline-formula> denote the corresponding orthogonal projections. In this paper, we study pairs of projections that satisfy the scalar identity <inline-formula> <tex-math notation="LaTeX">$\Pi _{M} \Pi _{N} \Pi _{M} = \gamma \Pi _{M}$ </tex-math></inline-formula> for some <inline-formula> <tex-math notation="LaTeX">$\gamma \in (0,1$ </tex-math></inline-formula>]. We establish several equivalent formulations of this property using block operator matrices, angles between subspaces, and extremal norm equalities. In addition, we compute explicit formulas for the norms of the sum and the anticommutator of such projections. We also show that this scalar condition implies the pair of projections is acute, and we prove that the property is preserved under subprojections.
S. Aljawi, A. Alotaibi, Cristian Conde et al.· IEEE Access· 0 citations
Group synchronization (GS) is the problem of estimating a set of <inline-formula><tex-math notation="LaTeX">$N$</tex-math></inline-formula> unknown elements <inline-formula><tex-math notation="LaTeX">$g_{1},\ldots\,, g_{N} \in \mathcal {G}$</tex-math></inline-formula> in a group <inline-formula><tex-math notation="LaTeX">$\mathcal {G}$</tex-math></inline-formula>, given noisy measurements of a subset of their pairwise ratios <inline-formula><tex-math notation="LaTeX">$g_{i}^{-1} g_{j}$</tex-math></inline-formula>. GS problems lie at the core of many state estimation tasks in robotics and computer vision, including 3D vision, robotic mapping, inertial navigation, and molecular reconstruction. Unfortunately, GS problems are typically both high-dimensional and non-convex, and therefore hard to solve in general. In this paper, we present <italic>Fast-Sync</italic>, a fast linear approximation method for GS that is suitable for initializing local manifold-based optimizers or certifiable global methods. Our approach generalizes chordal initialization [1,2] to arbitrary matrix Lie groups, and additionally proposes two new key algorithmic enhancements: we show how to exploit both the Kronecker-product structure in the problem data matrix and the topology of the synchronization graph to improve speed, scalability, and accuracy. Experimental evaluation across several GS tasks demonstrates that <italic>Fast-Sync</italic> provides high-quality initializations that enable local optimizers to efficiently recover globally optimal GS solutions, achieving high success rates even with considerable measurement noise.
Shane Holmes, Yiran Luo, Firat Taxpulat et al.· IEEE Robotics and Automation...· 0 citations
<p>A <em><span class="math inline">\(2\)</span>-factored dominating set</em> (<span class="math inline">\(2\)</span>fd-set) of a graph <span class="math inline">\(G=(V,E)\)</span> is a dominating set <span class="math inline">\(F\subseteq V\)</span> such that the induced subgraph <span class="math inline">\(G[F]\)</span> is <span class="math inline">\(2\)</span>-regular, and hence is a disjoint union of cycles. In this study, <span class="math inline">\(2\)</span>-factored dominating sets on fixed-width grid graphs of dimensions <span class="math inline">\(m \times n\)</span>, where <span class="math inline">\(m \in \{2,3,4\}\)</span>, are enumerated. We establish theorems describing the generating functions with respect to the number of <span class="math inline">\(2\)</span>-factored dominating sets in these grid graphs. The number of <span class="math inline">\(2\)</span>-factored dominating sets grows exponentially with <span class="math inline">\(n\)</span>, with growth constant determined by the dominant singularity of the generating function.</p>
M. Oo, Natawat Klamsakul, Nuttanon Songsuwan et al.· Journal of Combinatorial Mat...· 0 citations
It is a challenging problem to solve the multivariate linear model (MLM) <inline-formula> <tex-math notation="LaTeX">$\|\mathbf {Ax}= \mathbf {b}\|$ </tex-math></inline-formula> with the <inline-formula> <tex-math notation="LaTeX">$\ell ^{1}$ </tex-math></inline-formula>-norm approximation method such that <inline-formula> <tex-math notation="LaTeX">$\|\mathbf {Ax}-\mathbf {b}\|_{1}$ </tex-math></inline-formula>, the <inline-formula> <tex-math notation="LaTeX">$\ell ^{1}$ </tex-math></inline-formula>-norm of the residual error vector (REV), is minimized. In this work, our contributions lie in three aspects: firstly, a REV-based equivalence theorem for the structure of the <inline-formula> <tex-math notation="LaTeX">$\ell ^{1}$ </tex-math></inline-formula>-norm optimal solution to the MLM is proposed and proved, which establishes a theoretical connection between MLM <inline-formula> <tex-math notation="LaTeX">$\ell ^{1}$ </tex-math></inline-formula>-norm approximation and residual-domain basis-pursuit-type <inline-formula> <tex-math notation="LaTeX">$\ell ^{1}$ </tex-math></inline-formula>-optimization, with the MLM solution reconstructed through the Moore–Penrose inverse; secondly, the REV formulation is extended to the weighted <inline-formula> <tex-math notation="LaTeX">$\ell ^{1}$ </tex-math></inline-formula>-norm approximation problem by using diagonal scaling of the residual vector; thirdly, a unified algorithmic framework for solving the MLM with <inline-formula> <tex-math notation="LaTeX">$\ell ^{1}$ </tex-math></inline-formula>-norm optimization is proposed and six REV-based algorithms (L1-GPSR, L1-TNIPM, L1-HP, L1-IST, L1-ADM, L1-POB) are designed, where established optimization techniques are reformulated under a common residual-domain model, input-output structure, and Moore–Penrose inverse reconstruction scheme. There are three significant characteristics in the algorithms discussed: they are implemented with simple matrix operations which do not depend on specific optimization solvers; they are described with algorithmic pseudo-codes and implemented with Python and Octave/MATLAB which means easy usage; and the high accuracy and efficiency of our six REV-based algorithms can be achieved successfully in the scenarios with different levels of data redundancy. Numerical and real-data experiments further illustrate the accuracy, efficiency, and robustness of the proposed <inline-formula> <tex-math notation="LaTeX">$\ell ^{1}$ </tex-math></inline-formula>-based estimators, especially their reduced sensitivity to influential observations compared with the least-squares estimator. We hope that the unified theoretic and algorithmic framework with source code released on GitHub could motivate the applications of the <inline-formula> <tex-math notation="LaTeX">$\ell ^{1}$ </tex-math></inline-formula>-norm optimization for <inline-formula> <tex-math notation="LaTeX">$\ell ^{1}$ </tex-math></inline-formula>-based parameter estimation of MLM arising in science, technology, engineering, mathematics, economics, and so on.
Zhi-Qiang Feng, Hongyan Zhang, Ji Ma et al.· IEEE Access· 0 citations
<p>A vertex set <span class="math inline">\(D\)</span> in a finite undirected graph <span class="math inline">\(G\)</span> is an <span><em>efficient dominating set</em></span> (<em>e.d.s.</em> for short) of <span class="math inline">\(G\)</span> if every vertex of <span class="math inline">\(G\)</span> is dominated by exactly one vertex of <span class="math inline">\(D\)</span>. The <em>Efficient Domination</em> (ED) problem asks for the existence of an e.d.s. in <span class="math inline">\(G\)</span>. The <span><em>Weighted Efficient Dominating Set</em></span> (<span>WED</span> for short) problem further asks for an e.d.s. of minimum/maximum weight in a given graph <span class="math inline">\(G\)</span>. The ED problem is known to be NP-complete, even for claw-free graphs, for <span class="math inline">\(P_7\)</span>-free graphs, for chordal bipartite graphs, for planar bipartite graphs of maximum degree 3 and girth at least <span class="math inline">\(g\)</span> for every fixed <span class="math inline">\(g\)</span>, and thus for <span class="math inline">\(C_4\)</span>-free bipartite graphs. This manuscript reports a study on the WED problem for <span class="math inline">\(C_4\)</span>-free bipartite graphs (in the context of a study for bipartite graphs) and shows that the WED problem can be solved in polynomial time for (<span class="math inline">\(S_{1,2,5},C_4\)</span>)-free bipartite graphs, for (<span class="math inline">\(P_{10},C_4\)</span>)-free bipartite graphs, and for some related graphs classes.</p>
A. Brandstädt, R. Mosca· Journal of Combinatorial Mat...· 0 citations
