On squares of complementary graphs
A graph G is 2-stratified if its vertex set is partitioned into two classes (each of which is a stratum or a color class), where the vertices in one class are colored red and those in the other class are colored blue. Let F be a 2-stratified graph rooted at some blue vertex v. An F-coloring of a graph is a red-blue coloring of the vertices of G in which every blue vertex v belongs to a copy of F rooted at v. The F-domination number is the minimum number of red vertices in an F-coloring of G. In...
The (directed) distance from a vertex to a vertex in a strong digraph is the length of a shortest - (directed) path in . The eccentricity of a vertex of is the distance from to a vertex furthest from in . The radius rad is the minimum eccentricity among the vertices of and the diameter diam is the maximum eccentricity. A central vertex is a vertex with eccentricity and the subdigraph induced by the central vertices is the center . For a central vertex in a strong digraph...
2010 Mathematics Subject Classification: 05C50.We say that a regular graph G of order n and degree r і 1 (which is not the complete graph) is strongly regular if there exist non-negative integers t and q such that |SiЗSj| = t for any two adjacent vertices i and j, and |SiЗSj| = q for any two distinct non-adjacent vertices i and j, where Sk denotes the neighborhood of the vertex k. Let l1 = r, l2 and l3 be the distinct eigenvalues of a connected strongly regular graph. Let m1 = 1, m2 and m3 denote...
One of the main aims of the present and the next part [15] is to show that the theory of graphs (its language and results) can be very useful in algebraic investigations. We characterize, in terms of isomorphisms of some digraphs, all pairs , where is a finite unary algebra and a finite lattice such that the subalgebra lattice of is isomorphic to . Moreover, we find necessary and sufficient conditions for two arbitrary finite unary algebras to have isomorphic subalgebra lattices. We solve...
We use graph-algebraic results proved in [8] and some results of the graph theory to characterize all pairs of lattices for which there is a finite partial unary algebra such that its weak and strong subalgebra lattices are isomorphic to and , respectively. Next, we describe other pairs of subalgebra lattices (weak and relative, etc.) of a finite unary algebra. Finally, necessary and sufficient conditions are found for quadruples of lattices for which there is a finite unary algebra having...
We consider, for a positive integer , induced subgraphs in which each component has order at most . Such a subgraph is said to be -divided. We show that finding large induced subgraphs with this property is NP-complete. We also consider a related graph-coloring problem: how many colors are required in a vertex coloring in which each color class induces a -divided subgraph. We show that the problem of determining whether some given number of colors suffice is NP-complete, even for -coloring...
Let G = (V (G),E(G)) be a simple graph and H be a subgraph of G. G admits an H-covering, if every edge in E(G) belongs to at least one subgraph of G that is isomorphic to H. An (a, d)-H-antimagic total labeling of G is a bijection λ: V (G) ∪ E(G) → {1, 2, 3, . . . , |V (G)| + |E(G)|} such that for all subgraphs H′ isomorphic to H, the H′ weights [...] constitute an arithmetic progression a, a+d, a+2d, . . . , a+(n−1)d where a and d are positive integers and n is the number of subgraphs of G isomorphic...
A (p, q)-graph G is (a,d)-edge antimagic total if there exists a bijection f: V(G) ∪ E(G) → {1, 2,...,p + q} such that the edge weights Λ(uv) = f(u) + f(uv) + f(v), uv ∈ E(G) form an arithmetic progression with first term a and common difference d. It is said to be a super (a, d)-edge antimagic total if the vertex labels are {1, 2,..., p} and the edge labels are {p + 1, p + 2,...,p + q}. In this paper, we study the super (a,d)-edge antimagic total labeling of special classes of graphs derived from...