Search

A coalition in a graph G = (V;E) consists of two disjoint sets of vertices V1 and V2, neither of which is a dominating set of G but whose union V1 ∪ V2 is a dominating set of G. A coalition partition in a graph G of order n = |V | is a vertex partition π = {V1; V2, . . ., Vkg of V such that every set Vi either is a dominating set consisting of a single vertex of degree n - 1, or is not a dominating set but forms a coalition with another set Vj which is not a dominating set. Associated with every coalition partition &#960, of a graph G is a graph called the coalition graph of G with respect to &#960, denoted CG(G, &#960,), the vertices of which correspond one-to-one with the sets V1, V2, . . ., Vk of &#960, and two vertices are adjacent in CG(G, &#960,) if and only if their corresponding sets in &#960, form a coalition. In this paper we study coalition graphs, focusing on the coalition graphs of paths, cycles, and trees. We show that there are only finitely many coalition graphs of paths and finitely many coalition graphs of cycles and we identify precisely what they are. On the other hand, we show that there are infinitely many coalition graphs of trees and characterize this family of graphs. [ABSTRACT FROM AUTHOR]

Let G be either a complete graph of odd order or a complete bipartite graph in which each vertex partition has an even number of vertices. In this paper, we determine the set of triples (p, q, r), with p, q, r > 0, for which there exists a decomposition of G into p paths, q stars, and r cycles, each of which has 4 edges. [ABSTRACT FROM AUTHOR]

In the note we consider vertex coloring of a graph in which each color has an associated cost which is incurred each time the color is assigned to a vertex. The cost of coloring is the sum of costs incurred at each vertex. We show that the minimum cost coloring problem for n-vertex bipartite graph of degree Δ ≤ 4 can be solved in O(n2) time. This extends Jansen's result [K. Jansen, The optimum cost chromatic partition problem, in: Proc. CIAC'97, Lecture Notes in Comput. Sci. 1203 (1997) 25-36] for paths and cycles to subgraphs of biquartic graphs. [ABSTRACT FROM AUTHOR]

Let H be a graph. A decomposition of H is a set of edge-disjoint sub- graphs of H whose union is H. A Hamiltonian path (respectively, cycle) of H is a path (respectively, cycle) that contains every vertex of H exactly once. A k-star, denoted by Sk, is a star with k edges. In this paper, we give necessary and sufficient conditions for decomposing the complete graph into α copies of Hamiltonian path (cycle) and β copies of S3. [ABSTRACT FROM AUTHOR]

Let Γ = (G, σ) be a signed graph, where G is the underlying simple graph and σ : E(G) → {--, +} is the sign function on the edges of G. The adjacency matrix of a signed graph has -1 or +1 for adjacent vertices, depending on the sign of the edges. It was conjectured that if Γ is a signed complete graph of order n with k negative edges, k < n -- 1 and Γ has maximum index, then negative edges form K1,k. In this paper, we prove this conjecture if we confine ourselves to all signed complete graphs of order n whose negative edges form a tree of order k + 1. A [1, 2]-subgraph of G is a graph whose components are paths and cycles. Let Γ be a signed complete graph whose negative edges form a [1, 2]-subgraph. We show that the eigenvalues of Γ satisfy the following inequalities: --5 ≤ λn ≤ ... ≤ λ2 ≤ 3. [ABSTRACT FROM AUTHOR]

A total-colored graph G is rainbow total-connected if any two vertices of G are connected by a path whose edges and internal vertices have distinct colors. The rainbow total-connection number, denoted by rtc(G), of a graph G is the minimum number of colors needed to make G rainbow total-connected. In this paper, we prove that rtc(G) can be bounded by a constant 7 if the following three cases are excluded: diam(G) = 2, diam(G) = 3, G contains exactly two connected components and one of them is a trivial graph. An example is given to show that this bound is best possible. We also study Erdös-Gallai type problem for the rainbow total-connection number, and compute the lower bounds and precise values for the function f(n, k), where f(n, k) is the minimum value satisfying the following property: if |E(G)| ≥ f(n, k), then rtc(G) ≤ k. [ABSTRACT FROM AUTHOR]

Let G be a nontrivial connected, edge-colored graph. An edge-cut R of G is called a rainbow cut if no two edges in R are colored the same. An edge-coloring of G is a rainbow disconnection coloring if for every two distinct vertices u and v of G, there exists a rainbow cut in G, where u and v belong to different components of G – R. We introduce and study the rainbow disconnection number rd(G) of G, which is defined as the minimum number of colors required of a rainbow disconnection coloring of G. It is shown that the rainbow disconnection number of a nontrivial connected graph G equals the maximum rainbow disconnection number among the blocks of G. It is also shown that for a nontrivial connected graph G of order n, rd(G) = n–1 if and only if G contains at least two vertices of degree n – 1. The rainbow disconnection numbers of all grids Pm ロ Pn are determined. Furthermore, it is shown for integers k and n with 1 ≤ k ≤ n - 1 that the minimum size of a connected graph of order n having rainbow disconnection number k is n + k – 2. Other results and a conjecture are also presented. [ABSTRACT FROM AUTHOR]

A star edge-coloring of a graph G is a proper edge coloring such that every 2-colored connected subgraph of G is a path of length at most 3. For a graph G, let the list star chromatic index of G, ch′st(G), be the minimum k such that for any k-uniform list assignment L for the set of edges, G has a star edge-coloring from L. Dvořák, Mohar and Šámal asked whether the list star chromatic index of every subcubic graph is at most 7. We prove that it is at most 8. We also prove that if the maximum average degree of a subcubic graph G is less than 7/3 (respectively, 5/2), then ch′ st(G) ≤ 5 (respectively, ch′ st(G) ≤ 6). [ABSTRACT FROM AUTHOR]

In this paper, through the coupling and martingale method, we prove the order of the largest component in some critical random intersection graphs is n2/3 with high probability and the width of scaling window around the critical probability is n-1/3; while in some graphs, the order of the largest component and the width of the scaling window around the critical probability depend on the parameters in the corresponding definition of random intersection graphs. Our results show that there is still an "inside" phase transition in critical random intersection graphs. [ABSTRACT FROM AUTHOR]

Ho proved in [A note on the total domination number, Util. Math. 77 (2008) 97-100] that the total domination number of the Cartesian product of any two graphs without isolated vertices is at least one half of the product of their total domination numbers. We extend a result of Lu and Hou from [Total domination in the Cartesian product of a graph and K2 or Cn, Util. Math. 83 (2010) 313-322] by characterizing the pairs of graphs G and H for which γt(GロH) = 1 2γt(G)γt(H), whenever γt(H) = 2. In addition, we present an infinite family of graphs Gn with γt(Gn) = 2n, which asymptotically approximate equality in γt(GnロGn) ≥ 1/2γt(Gn)2. [ABSTRACT FROM AUTHOR]

An eternal m-secure set of a graph G = (V,E) is a set S0 ⊆ V that can defend against any sequence of single-vertex attacks by means of multiple guard shifts along the edges of G. The eternal m-security number σm(G) is the minimum cardinality of an eternal m-secure set in G. The eternal msecurity bondage number bσm(G) of a graph G is the minimum cardinality of a set of edges of G whose removal from G increases the eternal m-security number of G. In this paper, we study properties of the eternal m-security bondage number. In particular, we present some upper bounds on the eternal m-security bondage number in terms of eternal m-security number and edge connectivity number, and we show that the eternal m-security bondage number of trees is at most 2 and we classify all trees attaining this bound. [ABSTRACT FROM AUTHOR]

A total-k-coloring of a graph G is a coloring of V ∪ E using k colors such that no two adjacent or incident elements receive the same color. The total chromatic number χ′′(G) of G is the smallest integer k such that G has a total-k-coloring. Let G be a graph embedded in a surface of Euler characteristic ε ≥ 0. If G contains no 3-cycles adjacent to 4-cycles, that is, no 3-cycle has a common edge with a 4-cycle, then χ′′(G) ≤ max{8, Δ+1}. [ABSTRACT FROM AUTHOR]

An edge-colored graph G is conflict-free connected if any two of its vertices are connected by a path, which contains a color used on exactly one of its edges. In this paper the question for the smallest number of colors needed for a coloring of edges of G in order to make it conflict-free connected is investigated. We show that the answer is easy for 2-edge-connected graphs and very difficult for other connected graphs, including trees. [ABSTRACT FROM AUTHOR]

Let G = (V,E) be a graph and S ⊆ V. We say that S is a dominating set of G, if each vertex in V \ S has a neighbor in S. Moreover, we say that S is a connected (respectively, 2-edge connected or 2-connected) dominating set of G if G[S] is connected (respectively, 2-edge connected or 2-connected). The domination (respectively, connected domination, or 2-edge connected domination, or 2-connected domination) number of G is the cardinality of a minimum dominating (respectively, connected dominating, or 2-edge connected dominating, or 2-connected dominating) set of G, and is denoted γ(G) (respectively γ1(G), or γ′ 2(G), or γ2(G)). A well-known result of Duchet and Meyniel states that γ1(G) ≤ 3γ(G) - 2 for any connected graph G. We show that if γ(G) ≥ 2, then γ′ 2(G) ≤ 5γ(G) - 4 when G is a 2-edge connected graph and γ2(G) ≤ 11γ(G) - 13 when G is a 2-connected triangle-free graph. [ABSTRACT FROM AUTHOR]

There are only few results concerning crossing numbers of join of some graphs. In this paper, for some graphs on five vertices, we give the crossing numbers of its join with n isolated vertices. [ABSTRACT FROM AUTHOR]

Slater introduced the point-addition operation on graphs to characterize 4-connected graphs. The Γ-extension operation on binary matroids is a generalization of the point-addition operation. In general, under the Γ-extension operation the properties like graphicness and cographicness of matroids are not preserved. In this paper, we obtain forbidden minor characterizations for binary matroids whose Γ-extension matroids are graphic (respectively, cographic). [ABSTRACT FROM AUTHOR]

In this paper, we consider T-colorings of directed graphs. In particular, we consider as a T-set the set Tr = {0, 1, 2, . . ., r-1, r+1, . . .}. Exact values and bounds of the Tr-span of directed graphs whose underlying graph is a wheel graph are presented. [ABSTRACT FROM AUTHOR]

A graph G is a homomorphic preimage of another graph H, or equivalently G is H-colorable, if there exists a graph homomorphism f : G → H. A geometric graph Ḡ is a simple graph G together with a straight line drawing of G in the plane with the vertices in general position. A geometric homomorphism (respectively, isomorphism) Ḡ → H̄ is a graph homomorphism (respectively, isomorphism) that preserves edge crossings (respectively, and non-crossings). The homomorphism poset ℊ of a graph G is the set of isomorphism classes of geometric realizations of G partially ordered by the existence of injective geometric homomorphisms. A geometric graph Ḡ is ℋ-colorable if Ḡ → H̄ for some H̄ ∈ ℋ. In this paper, we provide necessary and sufficient conditions for Ḡ to be 𝒫n-colorable for n ≥ 2. Along the way, we also provide necessary and sufficient conditions for Ḡ to be 𝒦2,3-colorable. [ABSTRACT FROM AUTHOR]

An L(2, 1)-coloring (or labeling) of a simple connected graph G is a mapping f : V (G) → Z+ ∪ {0} such that |f(u)-f(v)| ≥ 2 for all edges uv of G, and |f(u) - f(v)| ≥ 1 if u and v are at distance two in G. The span of an L(2, 1)-coloring f, denoted by span(f), of G is max{f(v) : v ∈ V (G)}. The span of G, denoted by λ(G), is the minimum span of all possible L(2, 1)-colorings of G. For an L(2, 1)-coloring f of a graph G with span k, an integer l is a hole in f if l ∈ (0, k) and there is no vertex v in G such that f(v) = l. An L(2, 1)-coloring is a no-hole coloring if there is no hole in it, and is an irreducible coloring if color of none of the vertices in the graph can be decreased and yield another L(2, 1)-coloring of the same graph. An irreducible no-hole coloring, in short inh-coloring, of G is an L(2, 1)-coloring of G which is both irreducible and no-hole. For an inh-colorable graph G, the inh-span of G, denoted by λinh(G), is defined as λinh(G) = min{span(f) : f is an inh-coloring of G. Given a function h : E(G) → ℕ - {1}, and a positive integer r ≥ 2, the edge-multiplicity-paths-replacement graph G(rPh) of G is the graph obtained by replacing every edge uv of G with r paths of length h(uv) each. In this paper we show that G(rPh) is inh-colorable except possibly the cases h(e) ≥ 2 with equality for at least one but not for all edges e and (i) Δ(G) = 2, r = 2 or (ii) Δ (G) ≥ 3, 2 ≤ r ≤ 4. We find the exact value of λinh(G(rPh)) in several cases and give upper bounds of the same in the remaining. Moreover, we find the value of λ(G(rPh)) in most of the cases which were left by Lü and Sun in [L(2, 1)-labelings of the edge-multiplicity-paths-replacement of a graph, J. Comb. Optim. 31 (2016) 396-404]. [ABSTRACT FROM AUTHOR]

Let G be a simple graph on n vertices. An independent set in a graph is a set of pairwise non-adjacent vertices. The independence polynomial of G is the polynomial I(G,x)=∑nk=0s(G,k)xk, where s(G, k) is the number of independent sets of G with size k and s(G, 0) = 1. A unicyclic graph is a graph containing exactly one cycle. Let Cn be the cycle on n vertices. In this paper we study the independence polynomial of unicyclic graphs. We show that among all connected unicyclic graphs G on n vertices (except two of them), I(G, t) > I(Cn, t) for sufficiently large t. Finally for every n ≥ 3 we find all connected graphs H such that I(H, x) = I(Cn, x). [ABSTRACT FROM AUTHOR]

In this paper, we prove that for an integer r ≥ 1, every regular tournament T of degree 3r - 1 contains at least 21/16r-10/3 disjoint directed 4-cycles. Our result is an improvement of Lichiardopol's theorem when taking q = 4 [Discrete Math. 310 (2010) 2567-2570]: for given integers q ≥ 3 and r ≥ 1, a tournament T with minimum out-degree and in-degree both at least (q - 1)r - 1 contains at least r disjoint directed cycles of length q. [ABSTRACT FROM AUTHOR]

The harmonic index of a graph G, denoted by H(G), is defined as the sum of weights 2/\d(u) + d(v)] over all edges uv of G, where d(u) denotes the degree of a vertex u. In this paper we establish a lower bound on the harmonic index of a tree T. [ABSTRACT FROM AUTHOR]

Let D = (V, A) be a digraph; if there is at least one arc between every pair of distinct vertices of D, then D is a semicomplete digraph. A digraph D is locally semicomplete if for every vertex x, the out-neighbours of x induce a semicomplete digraph and the in-neighbours of x induce a semicomplete digraph. A locally semicomplete digraph without 2-cycle is a local tournament. In 2012, Bang-Jensen and Huang [J. Combin Theory Ser. B 102 (2012) 701-714] concluded that every 2-arc-strong locally semicomplete digraph which is not the second power of an even cycle has two arc-disjoint strong spanning subdigraphs, and proposed the conjecture that every 3-strong local tournament has two arc-disjoint Hamiltonian cycles. According to Bang-Jensen, Guo, Gutin and Volkmann, locally semicomplete digraphs have three subclasses: the round decomposable; the non-round decomposable which are not semicomplete; the non-round decomposable which are semicomplete. In this paper, we prove that every 3-strong round decomposable locally semicomplete digraph has two arc-disjoint Hamiltonian cycles, which implies that the conjecture holds for the round decomposable local tournaments. Also, we characterize the 2-strong round decomposable local tournaments each of which contains a Hamiltonian path P and a Hamiltonian cycle arc-disjoint from P. [ABSTRACT FROM AUTHOR]

We continue our research in the enumeration of Hamiltonian cycles (HCs) on thin cylinder grid graphs Cm × Pn+1 by studying a triangular variant of the problem. There are two types of HCs, distinguished by whether they wrap around the cylinder. Using two characterizations of these HCs, we prove that, for fixed m, the number of HCs of both types satisfy some linear recurrence relations. For small m, computational results reveal that the two numbers are asymptotically the same. We conjecture that this is true for all m ≥ 2. [ABSTRACT FROM AUTHOR]

There are only few results concerning the crossing numbers of join of some graphs. In this paper, the crossing numbers of join products for the generalized Petersen graph P(3,1) with n isolated vertices as well as with the path Pn on n vertices and with the cycle Cn are determined. [ABSTRACT FROM AUTHOR]

A graph is equitably k-colorable if its vertices can be partitioned into k independent sets in such a way that the numbers of vertices in any two sets differ by at most one. The smallest k for which such a coloring exists is known as the equitable chromatic number of G and denoted by χ=(G). It is known that the problem of computation of X=(G) is NP-hard in general and remains so for corona graphs. In this paper we consider the same model of coloring in the case of corona multiproducts of graphs. In particular, we obtain some results regarding the equitable chromatic number for the l-corona product G ol H, where G is an equitably 3- or 4-colorable graph and H is an r-partite graph, a cycle or a complete graph. Our proofs are mostly constructive in that they lead to polynomial algorithms for equitable coloring of such graph products provided that there is given an equitable coloring of G. Moreover, we confirm the Equitable Coloring Conjecture for corona products of such graphs. This paper extends the results from [H. Furmańczyk, K. Kaliraj, M. Kubale and V.J. Vivin, Equitable coloring of corona products of graphs, Adv. Appl. Discrete Math. 11 (2013) 103-120]. [ABSTRACT FROM AUTHOR]

Graph packing generally deals with unlabeled graphs. In [4], the authors have introduced a new variant of the graph packing problem, called the labeled packing of a graph. This problem has recently been studied on trees [M.A. Tahraoui, E. Duchêne and H. Kheddouci, Labeled 2-packings of trees, Discrete Math. 338 (2015) 816-824] and cycles [E. Duchêne, H. Kheddouci, R.J. Nowakowski and M.A. Tahraoui, Labeled packing of graphs, Australas. J. Combin. 57 (2013) 109-126]. In this note, we present a lower bound on the labeled packing number of any (n, n - 2)-graph into Kn. This result improves the bound given by Wo'zniak in [Embedding graphs of small size, Discrete Appl. Math. 51 (1994) 233-241]. [ABSTRACT FROM AUTHOR]

A spanning subgraph F of a graph G is called a P≥3-factor of G if every component of F is a path of order at least 3. A graph G is called a P≥3- factor covered graph if G has a P≥3-factor including e for any e ∈ E(G). In this paper, we obtain three sufficient conditions for graphs to be P≥3-factor covered graphs. Furthermore, it is shown that the results are sharp. [ABSTRACT FROM AUTHOR]

There exists a significant body of work on determining the acquisition number at(G) of various graphs when the vertices of those graphs are each initially assigned a unit weight. We determine properties of the acquisition number of the path, star, complete, complete bipartite, cycle, and wheel graphs for variations on this initial weighting scheme, with the majority of our work focusing on the expected acquisition number of randomly weighted graphs. In particular, we bound the expected acquisition number E(at(Pn)) of the n-path when n distinguishable "units" of integral weight, or chips, are randomly distributed across its vertices between 0.242n and 0.375n. With computer support, we improve it by showing that E(at(Pn)) lies between 0.29523n and 0.29576n. We then use subadditivity to show that the limiting ratio limE(at(Pn))/n exists, and simulations reveal more exactly what the limiting value equals. The Hoeffding-Azuma inequality is used to prove that the acquisition number is tightly concentrated around its expected value. Additionally, in a different context, we offer a non-optimal acquisition protocol algorithm for the randomly weighted path and exactly compute the expected size of the resultant residual set. [ABSTRACT FROM AUTHOR]

Let G = (V,E) be a simple graph with vertex set V and edge set E. A signed total Roman edge dominating function of G is a function f : E → {-1, 1, 2} satisfying the conditions that (i) Σe′∈N(e) f(e′) ≥ 1 for each e ∈ E, where N(e) is the open neighborhood of e, and (ii) every edge e for which f(e) = -1 is adjacent to at least one edge e′ for which f(e′) = 2. The weight of a signed total Roman edge dominating function f is ω(f) = Σe∈E f(e). The signed total Roman edge domination number γ'stR(G) of G is the minimum weight of a signed total Roman edge dominating function of G. In this paper, we first prove that for every tree T of order and we characterize all extreme trees, and then we present some sharp bounds for the signed total Roman edge domination number. We also determine this parameter for some classes of graphs. [ABSTRACT FROM AUTHOR]

New graph characteristic, the total H-irregularity strength of a graph, is introduced. Estimations on this parameter are obtained and for some families of graphs the precise values of this parameter are proved. [ABSTRACT FROM AUTHOR]

The proper connection number of a graph is the least integer k for which the graph has an edge coloring with k colors, with the property that any two vertices are joined by a properly colored path. We prove that given two connected non-bipartite graphs, one of which is (vertex) 2-connected, the proper connection number of their direct product is 2. [ABSTRACT FROM AUTHOR]

Let k ≥ 1 be an integer. A signed total Roman k-dominating function on a graph G is a function f : V (G) -→ {-1, 1, 2} such that ∑u∊N(v) f(u) ≥ k for every v ∈ V (G), where N(v) is the neighborhood of v, and every vertex u ∈ V (G) for which f(u) = -1 is adjacent to at least one vertex w for which f(w) = 2. A set {f1, f2, . . ., fd} of distinct signed total Roman k-dominating functions on G with the property that Pd i=1 fi(v) ≤ k for each v ∈ V (G), is called a signed total Roman k-dominating family (of functions) on G. The maximum number of functions in a signed total Roman k-dominating family on G is the signed total Roman k-domatic number of G, denoted by dk stR(G). In this paper we initiate the study of signed total Roman k-domatic numbers in graphs, and we present sharp bounds for dk stR(G). In particular, we derive some Nordhaus-Gaddum type inequalities. In addition, we determine the signed total Roman k-domatic number of some graphs. [ABSTRACT FROM AUTHOR]

The generalized k-connectivity κk(G) of a graph G, mentioned by Hager in 1985, is a natural generalization of the path-version of the classical connectivity. As a natural counterpart of this concept, Li et al. in 2011 introduced the concept of generalized k-edge-connectivity which is defined as λk(G) = min{λG(S) | S ⊆ V (G) and |S| = k}, where λG(S) denote the maximum number ℓ of pairwise edge-disjoint trees T1, T2, . . ., Tℓ in G such that S ⊆ V (Ti) for 1 ≤ i ≤ ℓ. In this paper we get a sharp lower bound for the generalized 3-edge-connectivity of the strong product of any two connected graphs. [ABSTRACT FROM AUTHOR]

A digraph of order n is k-traceable if n ≥ k and each of its induced subdigraphs of order k is traceable. It is known that if 2 ≤ k ≤ 6, every k-traceable oriented graph is traceable but for k = 7 and for each k ≥ 9, there exist k-traceable oriented graphs that are nontraceable. We show that every 8-traceable oriented graph is traceable. [ABSTRACT FROM AUTHOR]

For a graph G, let γR(G) and γr2(G) denote the Roman domination number of G and the 2-rainbow domination number of G, respectively. It is known that γr2(G)≤γR(G)≤32γr2(G). Fujita and Furuya [Difference between 2-rainbow domination and Roman domination in graphs, Discrete Appl. Math. 161 (2013) 806-812] present some kind of characterization of the graphs G for which γR(G) - γr2(G) = k for some integer k. Unfortunately, their result does not lead to an algorithm that allows to recognize these graphs efficiently. We show that for every fixed non-negative integer k, the recognition of the connected K4-free graphs G with γR(G) - γr2(G) = k is NP-hard, which implies that there is most likely no good characterization of these graphs. We characterize the graphs G such that γr2(H) = γR(H) for every induced subgraph H of G, and collect several properties of the graphs G with γR(G)=32γr2(G). [ABSTRACT FROM AUTHOR]

A graph is said to be characterized by its permanental spectrum if there is no other non-isomorphic graph with the same permanental spectrum. In this paper, we investigate when a complete bipartite graph Kp,p with some edges deleted is determined by its permanental spectrum. We first prove that a graph obtained from Kp,p by deleting all edges of a star K1,l, provided l < p, is determined by its permanental spectrum. Furthermore, we show that all graphs with a perfect matching obtained from Kp,p by removing five or fewer edges are determined by their permanental spectra. [ABSTRACT FROM AUTHOR]

Let D = (V,A) be a finite simple directed graph (shortly, digraph). A function f : V → {-1, 0, 1} is called a twin minus total dominating function (TMTDF) if f(N-(v)) ≥ 1 and f(N+(v)) ≥ 1 for each vertex v ∈ V. The twin minus total domination number of D is λ*mt(D) = min{w(f) | f is a TMTDF of D}. In this paper, we initiate the study of twin minus total domination numbers in digraphs and we present some lower bounds for λ*mt(D) in terms of the order, size and maximum and minimum in-degrees and out-degrees. In addition, we determine the twin minus total domination numbers of some classes of digraphs. [ABSTRACT FROM AUTHOR]

We introduce the concept of constant 2-labelling of a vertex-weighted graph and show how it can be used to obtain perfect weighted coverings. Roughly speaking, a constant 2-labelling of a vertex-weighted graph is a black and white colouring of its vertex set which preserves the sum of the weights of black vertices under some automorphisms. We study constant 2-labellings on four types of vertex-weighted cycles. Our results on cycles allow us to determine (r, a, b)-codes in Z2 whenever |a - b| > 4, r ≥ 2 and we give the precise values of a and b. This is a refinement of Axenovich's theorem proved in 2003. [ABSTRACT FROM AUTHOR]

A Roman dominating function (or just RDF) on a graph G = (V,E) is a function f : V → {0, 1, 2} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of an RDF f is the value f(V (G)) = ∑u∈V (G) f(u). The Roman domination number of a graph G, denoted by R(G), is the minimum weight of a Roman dominating function on G. A graph G is Roman domination stable if the Roman domination number of G remains unchanged under removal of any vertex. In this paper we present upper bounds for the Roman domination number in the class of Roman domination stable graphs, improving bounds posed in [V. Samodivkin, Roman domination in graphs: the class ℜU V R, Discrete Math. Algorithms Appl. 8 (2016) 1650049]. [ABSTRACT FROM AUTHOR]

In 2009, Barrière, Dalfó, Fiol, and Mitjana introduced the generalized hierarchical product of graphs. This operation is a generalization of the Cartesian product of graphs. It is known that every connected graph has a unique prime factor decomposition with respect to the Cartesian product. We generalize this result to show that connected graphs indeed have a unique prime factor decomposition with respect to the generalized hierar-chical product. We also give preliminary results on the domination number of generalized hierarchical products. [ABSTRACT FROM AUTHOR]

A strong edge-coloring of a graph is a proper edge-coloring where each color class induces a matching. We denote by χ′s (G) the strong chromatic index of G which is the smallest integer k such that G can be strongly edgecolored with k colors. It is known that every planar graph G has a strong edge-coloring with at most 4∆(G) + 4 colors [R.J. Faudree, A. Gyárfás, R.H. Schelp and Zs. Tuza, The strong chromatic index of graphs, Ars Combin. 29B (1990) 205-211]. In this paper, we show that if G is a planar graph with g ≥ 5, then χ′s (G) ≤ 4∆(G) - 2 when ∆(G) ≥ 6 and χ′s (G) ≤ 19 when ∆(G) = 5, where g is the girth of G. [ABSTRACT FROM AUTHOR]

For a digraph D, V (D) and A(D) will denote the sets of vertices and arcs of D respectively. In an arc-colored digraph, a subset K of V(D) is said to be kernel by monochromatic paths (mp-kernel) if (1) for any two different vertices x, y in N there is no monochromatic directed path between them (N is mp-independent) and (2) for each vertex u in V (D) \ N there exists v ∈ N such that there is a monochromatic directed path from u to v in D (N is mp-absorbent). If every arc in D has a different color, then a kernel by monochromatic paths is said to be a kernel. Two associated digraphs to an arc-colored digraph are the closure and the color-class digraph CC(D). In this paper we will approach an mp-kernel via the closure of induced subdigraphs of D which have the property of having few colors in their arcs with respect to D. We will introduce the concept of color-perfect digraph and we are going to prove that if D is an arc-colored digraph such that D is a quasi color-perfect digraph and CC(D) is not strong, then D has an mp-kernel. Previous interesting results are generalized, as for example Richardson′s Theorem. [ABSTRACT FROM AUTHOR]

A k-uniform hypergraph H = (V ;E) is called self-complementary if there is a permutation σ : V → V , called a complementing permutation, such that for every k-subset e of V , e ∈ E if and only if σ(e) ∉ E. In other words, H is isomorphic with H′ = (V ; V(k) − E). In this paper we define a bi-regular hypergraph and prove that there exists a bi-regular self-complementary 3-uniform hypergraph on n vertices if and only if n is congruent to 0 or 2 modulo 4. We also prove that there exists a quasi regular self-complementary 3-uniform hypergraph on n vertices if and only if n is congruent to 0 modulo 4. [ABSTRACT FROM AUTHOR]

In this paper, we consider the least integer d such that every longest cycle of a k-connected graph of order n (and of independent number α) contains all vertices of degree at least d. [ABSTRACT FROM AUTHOR]

A distance magic labeling of a graph G = (V,E) with |V | = n is a bijection ℓ : V → {1, . . . , n} such that the weight of every vertex v, computed as the sum of the labels on the vertices in the open neighborhood of v, is a constant. In this paper, we show that hypercubes with dimension divisible by four are not distance magic. We also provide some positive results by proving necessary and sufficient conditions for the Cartesian product of certain complete multipartite graphs and the cycle on four vertices to be distance magic. [ABSTRACT FROM AUTHOR]

In their paper, Bounds on the number of edges in hypertrees, G.Y. Katona and P.G.N. Szabó introduced a new, natural definition of hypertrees in k- uniform hypergraphs and gave lower and upper bounds on the number of edges. They also defined edge-minimal, edge-maximal and l-hypertrees and proved an upper bound on the edge number of l-hypertrees. In the present paper, we verify the asymptotic sharpness of the upper bound on the number of edges of k-uniform hypertrees given in the above mentioned paper. We also make an improvement on the upper bound of the edge number of 2-hypertrees and give a general extension construction with its consequences. We give lower and upper bounds on the maximal number of edges of k-uniform edge-minimal hypertrees and a lower bound on the number of edges of k-uniform edge-maximal hypertrees. In the former case, the sharp upper bound is conjectured to be asymptotically . [ABSTRACT FROM AUTHOR]

A total-colored path is total rainbow if both its edges and internal vertices have distinct colors. The total rainbow connection number of a connected graph G, denoted by trc(G), is the smallest number of colors that are needed in a total-coloring of G in order to make G total rainbow connected, that is, any two vertices of G are connected by a total rainbow path. In this paper, we study the computational complexity of total rainbow connection of graphs. We show that deciding whether a given total-coloring of a graph G makes it total rainbow connected is NP-Complete. We also prove that given a graph G, deciding whether trc(G) = 3 is NP-Complete. [ABSTRACT FROM AUTHOR]

A polyomino graph P is a connected finite subgraph of the infinite plane grid such that each finite face is surrounded by a regular square of side length one and each edge belongs to at least one square. A dimer covering of P corresponds to a perfect matching. Different dimer coverings can interact via an alternating cycle (or square) with respect to them. A set of disjoint squares of P is a resonant set if P has a perfect matching M so that each one of those squares is M-alternating. In this paper, we show that if K is a maximum resonant set of P, then P − K has a unique perfect matching. We further prove that the maximum forcing number of a polyomino graph is equal to the cardinality of a maximum resonant set. This confirms a conjecture of Xu et al. [26]. We also show that if K is a maximal alternating set of P, then P − K has a unique perfect matching. [ABSTRACT FROM AUTHOR]

An L(2, 1)-coloring (or labeling) of a graph G is a vertex coloring f : V (G) → Z+ ∪ {0} such that |f(u) − f(v)| ≥ 2 for all edges uv of G, and |f(u)−f(v)| ≥ 1 if d(u, v) = 2, where d(u, v) is the distance between vertices u and v in G. The span of an L(2, 1)-coloring is the maximum color (or label) assigned by it. The span of a graph G is the smallest integer λ such that there exists an L(2, 1)-coloring of G with span λ. An L(2, 1)-coloring of a graph with span equal to the span of the graph is called a span coloring. For an L(2, 1)-coloring f of a graph G with span k, an integer h is a hole in f if h ∈ (0, k) and there is no vertex v in G such that f(v) = h. A no-hole coloring is an L(2, 1)-coloring with no hole in it. An L(2, 1)-coloring is irreducible if color of none of the vertices in the graph can be decreased to yield another L(2, 1)-coloring of the same graph. A graph G is inh-colorable if there exists an irreducible no-hole coloring of G. Most of the results obtained in this paper are answers to some problems asked by Laskar et al. [5]. These problems are mainly about relationship between the span and maximum no-hole span of a graph, lower inh-span and upper inh-span of a graph, and the maximum number of holes and minimum number of holes in a span coloring of a graph. We also give some sufficient conditions for a tree and an unicyclic graph to have inh-span Δ + 1. [ABSTRACT FROM AUTHOR]