Determining whether or not a graph has an efficient dominating set (equivalently, a perfect code) is an NP-complete problem. Here we present a polynomial time algorithm to decide if a given simplicial graph has an efficient dominating set. However, the efficient domination number decision problem is NP-complete for simplicial graphs.

The purpose of this note is to give two binomial sums with generalized Fibonacci sequences. These results generalize two binomial sums by Kilic and Ionascu in The Fibonacci Quarterly, 48.2(2010), 161-167.

Let \( G \) be a connected graph of size at least 2 and \( c: E(G) \to \{0, 1, \ldots, k-1\} \) an edge coloring (or labeling) of \( G \) using \( k \) colors (where adjacent edges may be assigned the same color). For each vertex \( v \) of \( G \), the color code of \( v \) with respect to \( c \) is the \( k \)-tuple \( \text{code}(v) = (a_0, a_1, \ldots, a_{k-1}) \), where \( a_i \) is the number of edges incident with \( v \) that are labeled \( i \) (for \( 0 \leq i \leq k-1 \)). The labeling \( c \) is called a detectable labeling if distinct vertices in \( G \) have distinct color codes. The value \( \text{val}(c) \) of a detectable labeling \( c \) of a graph \( G \) is the sum of the colors assigned to the edges in \( G \). The total detection number \( \text{td}(G) \) of \( G \) is defined by \( \text{td}(G) = \min\{\text{val}(c)\} \), where the minimum is taken over all detectable labelings \( c \) of \( G \). Thus, if \( G \) is a connected graph of size \( m \geq 2 \), then \( 1 \leq \text{td}(G) \leq \binom{m}{2} \). We present characterizations of all connected graphs \( G \) of size \( m \geq 2 \) for which \( \text{td}(G) \in \{1, \binom{m}{2}\} \). The total detection numbers of complete graphs and cycles are also investigated.

In this paper we prove that every planar graph without \(5\)- and \(8\)-cycles and without adjacent triangles is \(3\)-colorable.

A new construction of authentication codes with arbitration using singular pseudo-symplectic geometry on finite fields is given. Some parameters and the probabilities of success for different types of deceptions are computed.

Two graphs are defined to be adjointly equivalent if their complements are chromatically equivalent. By \( h(G,x) \) and \( P(G,\lambda) \) we denote the adjoint polynomial and the chromatic polynomial of graph \( G \), respectively. A new invariant of graph \( G \), which is the fifth character \( R_5(G) \), is given in this paper. Using this invariant and the properties of the adjoint polynomials, we firstly and completely determine the adjoint equivalence class of the graph \( \zeta_n^1 \). According to the relations between \( h(G,x) \) and \( P(G,\lambda) \), we also simultaneously determine the chromatic equivalence class of \( \overline{\zeta_n^1} \).

In this paper, we discuss the properties of a class of generalized harmonic numbers \( H_{n,r} \). Using Riordan arrays and generating functions, we establish some identities involving \( H_{n,r} \). Furthermore, we investigate certain sums related to harmonic polynomials \( H_n(z) \). In particular, using the Riordan array method, we explore interesting relationships between these polynomials, the generating Stirling polynomials, the Bernoulli polynomials, and the Cauchy polynomials. Finally, we obtain the asymptotic expansion of certain sums involving \( H_{n,r} \).

We prove that \( F_v(3,5;6) = 16 \), which solves the smallest open case of vertex Folkman numbers of the form \( F_v(3, k; k+1) \). The proof uses computer algorithms.

A family \( \mathcal{G} \) of connected graphs is a family with constant metric dimension if \( \dim(G) \) is finite and does not depend upon the choice of \( G \) in \( \mathcal{G} \). The metric dimension of some classes of plane graphs has been determined in references [3], [4], [5], [12], [14], and [18], while the metric dimension of some families of convex polytopes has been studied in references [8], [9], [10], and [11]. The following open problem was raised in reference [11].

Open Problem [11]: Let \( G \) be the graph of a convex polytope which is obtained by joining the graph of two different convex polytopes \( G_1 \) and \( G_2 \) (such that the outer cycle of \( G_1 \) is the inner cycle of \( G_2 \)) both having constant metric dimension. Is it the case that \( G \) will always have constant metric dimension?

In this paper, we extend this study to an infinite class of convex polytopes obtained as a combination of the graph of an antiprism \( A_n \) [1] and the graph of convex polytope \( Q_n \) [2], such that the outer cycle of \( A_n \) is the inner cycle of \( Q_n \). It is natural to ask for the characterization of classes of convex polytopes with constant metric dimension. Note that the problem of determining whether \( \dim(G) < k \) is an NP-complete problem [7].