Let \(G = (V, E)\) be a graph. For any real valued function \(f: V \to \mathbb{R}\) and \(S \subseteq V\), let \(f(S) = \sum_{u \in S} f(u)\). Let \(c, d\) be positive integers such that \(\gcd(c, d) = 1\) and \(0 < \frac{c}{d} \leq 1\). A \(\frac{c}{d}\)-dominating function \(f\) is a function \(f: V \to \{-1, 1\}\) such that \(f[v] \geq 1\) for at least \(\frac{c}{d}\) of the vertices \(v \in V\). The \(\frac{c}{d}\)-domination number of \(G\), denoted by \(\gamma_{\frac{c}{d}}(G)\), is defined as \(\min\{f(V) | f\) is a \(\frac{c}{d}\)-dominating function on \(G\}\). We determine a sharp lower bound on \(\gamma_{\frac{c}{d}}(G)\) for regular graphs \(G\), determine the value of \(\gamma_{\frac{c}{d}}(G)\) for an arbitrary cycle \(C_n\), and show that the decision problem PARTIAL SIGNED DOMINATING FUNCTION is \(NP\)-complete.

The vertex set of a halved cube \(Q’_d\) consists of a bipartition vertex set of a cube \(Q_d\) and two vertices are adjacent if they have a common neighbour in the cube. Let \(d \geq 5\). Then it is proved that \(Q’_d\) is the only connected, \(\binom{d}{3}\)-regular graph on \(2^d\) vertices in which every edge lies in two \(d\)-cliques and two \(d\)-cliques do not intersect in a vertex.

Geometrical representations of certain classical number tables modulo a given prime power (binomials, Gaussian \(g\)-binomials and Stirling numbers of \(1st\) and \(2nd\) kind) generate patterns with self-similarity features. Moreover, these patterns appear to be strongly related for all number tables under consideration, when a prime power is fixed.

These experimental observations are made precise by interpreting the recursively defined number tables as the output of certain cellular automata \((CA)\). For a broad class of \(CA\) it has been proven \([11]\) that the long time evolution can generate fractal sets, whose properties can be understood by means of hierarchical iterated function systems. We use these results to show that the mentioned number tables (mod \(p^v\)) induce fractal sets which are homeomorphic to a universal fractal set denoted by \(\mathcal{S}_{p^v}\) which we call Sierpinski triangle (mod \(p^v\)).

It is known that each incidence matrix between any two levels of the Boolean lattice and the lattice of flats of a finite projective geometry has full rank. We show that this also holds for the lattice of flats of a finite affine geometry.

In this paper, we prove that if \(G\) is a \(k\)-connected (\(k \geq 2\)) graph of order \(n\) such that the sum of degrees of any \(k+1\) independent vertices is at least \(n+k\), and if the set of claw centers of \(G\) is independent, then \(G\) is hamiltonian.

A graph without \(4\)-cycles is called \(C_4\)-free. A \(C_4\)-free graph is \(C_4\)-saturated if adding any edge creates a 4-cycle. Ollmann showed that any \(n\)-node \(C_4\)-saturated graph has at least \(\frac{3}{2}n – 3\) edges. He also described the set of all \(n\)-node \(C_4\)-saturated graphs with \(\lceil \frac{3}{2}n \rceil – 3\) edges. A graph is \(P_3\)-connected if each pair of nonadjacent nodes is connected by a path with exactly \(3\) edges. A \(C_4\)-saturated graph is \(P_3\)-connected, but not vice versa. We generalize Ollmann’s results by proving that any \(n\)-node \(P_3\)-connected graph has at least \(\frac{3}{2}n – 3\) edges. We also describe the set of all \(n\)-node \(P_3\)-connected graphs with \(\lceil \frac{3}{2}n \rceil – 3\) edges. This is a superset of Ollmann’s set as some \(n\)-node \(P_3\)-connected graphs with \(\lceil \frac{3}{2}n \rceil – 3\) edges do have \(4\)-cycles.

For a given graph \(G\) an edge-coloring of \(G\) with colors \(1,2,3,\ldots\) is said to be a \emph{consecutive coloring} if the colors of edges incident with each vertex are distinct and form an interval of integers. In the case of bipartite graphs this kind of coloring has a number of applications in scheduling theory. In this paper we investigate the question whether a bipartite graph has a consecutive coloring with \(\Delta\) colors. We show that the above question can be answered in polynomial time for \(\Delta \leq 4\) and becomes NP-complete if \(\Delta > 4\).

In this article we give a direct construction of \(HPMD\). As an application, we discuss the existence of \((v,6,1)\)-\(PMD\) and obtain an infinite class of \((v,6,1)\)-\(PMD\) where \(v \equiv 4 \pmod{6}\).

A graph is \({{well \; covered}}\) if every maximal independent set has the same size and \({very \;well\; covered}\) if every maximal independent set contains exactly half the number of vertices. In this paper, we present an alternative characterization of a certain sub-class of well-covered graphs and show that this generalizes a characterization of very well covered graphs given by Favaron [3].

We call a node of a simple graph \({connectivity\;-redundant}\) if its removal does not diminish the connectivity. Studying the distribution of such nodes in a CKL-graph, i.e., a connected graph \(G\) of order \(\geq 3\) whose connectivity \(\kappa\) and minimum degree \(\delta\) satisfy the inequality \(\kappa \geq (\frac{3\kappa – 1}{2})\), we obtain a best lower bound, sharp for any \(\kappa > 1\), for the number of connectivity-redundant nodes in \(G\), which is \(\kappa + 1\) or \(\kappa + 2\) according to whether \(\kappa\) is odd or even, respectively. As a by-product we obtain a new proof of an old theorem of Watkins concerning node-transitive graphs.