Search

This paper focuses on a novel approach for producing a floor plan (FP), either a rectangular (RFP) or an orthogonal (OFP) based on the concept of orthogonal drawings, which satisfies the adjacency relations given by any bi-connected plane triangulation G. Previous algorithms for constructing a FP are primarily restricted to the cases given below: (i) A bi-connected plane triangulation without separating triangles (STs) and with at most 4 corner implying paths (CIPs), known as properly triangulated planar graph (PTPG). (ii) A bi-connected plane triangulation with an exterior face of length 3 and no CIPs, known as maximal planar graph (MPG). The FP obtained in the above two cases is a RFP or an OFP respectively. In this paper, we present the construction of a FP (RFP if exists, else an OFP), for a bi-connected plane triangulation G in linear-time. [ABSTRACT FROM AUTHOR]

Let k 1 be an integer, and let G be a finite and simple graph with vertex set V (G). A signed total Italian k-dominating function on a graph G is a function f: V (G) ! f1; 1; 2g such that P u2N(v) f(u) ≥ k for every v 2 V (G), where N(v) is the neighborhood of v, and each vertex u with f(u) = 1 is adjacent to a vertex v with f(v) = 2 or to two vertices w and z with f(w) = f(z) = 1. A set ff1; f2;: ::; fdg of distinct signed total Italian k-dominating functions on G with the property that Pd i=1 fi(v) ≤ k for each v 2 V (G), is called a signed total Italian k-dominating family (of functions) on G. The maximum number of functions in a signed total Italian k-dominating family on G is the signed total Italian k-domatic number of G, denoted by dk stI (G). In this paper we initiate the study of signed total Italian k-domatic numbers in graphs, and we present sharp bounds for dk stI (G). In addition, we determine the signed total Italian k-domatic number of some graphs. [ABSTRACT FROM AUTHOR]

An edge labeling of a connected graph G=(V,E) is said to be local antimagic if it is a bijection f:E→{1,...,|E|} such that for any pair of adjacent vertices x and y, f+(x)≠f+(y), where the induced vertex label f+(x)=∑f(e), with e ranging over all the edges incident to x. The local antimagic chromatic number of G, denoted by χla(G), is the minimum number of distinct induced vertex labels over all local antimagic labelings of G. In this paper, several sufficient conditions for χla(H)≤χla(G) are obtained, where H is obtained from G with a certain edge deleted or added. We then determined the exact value of the local antimagic chromatic number of many cycle related join graphs. [ABSTRACT FROM AUTHOR]

Let G = (V;E) be a given graph of order n. A function f: V ! f0; 1; 2g is an independent Roman dominating function (IRDF) on G if for every vertex v 2 V with f(v) = 0 there is a vertex u adjacent to v with f(u) = 2 and fv 2 V: f(v) > 0g is an independent set. The weight of an IRDF f on G is the value f(V) = P v2V f(v). The minimum weight of an IRDF among all IRDFs on G is called the independent Roman domination number of G. In this paper, we give algorithms for computing the independent Roman domination number of G in O(jV j) time when G = (V;E) is a tree, unicyclic graph or proper interval graph. [ABSTRACT FROM AUTHOR]

For a simple, undirected graph G(V;E), a function h: V (G) ! f0; 1; 2g such that each edge (u; v) of G is either incident with a vertex with weight at least one or there exists a vertex w such that either (u;w) 2 E(G) or (v;w) 2 E(G) and h(w) = 2, is called a vertex-edge Roman dominating function (ve-RDF) of G. For a graph G, the smallest possible weight of a ve-RDF of G which is denoted by veR(G), is known as the vertex-edge Roman domination number of G. The problem of determining veR(G) of a graph G is called minimum vertex-edge Roman domination problem (MVERDP). In this article, we show that the problem of deciding if G has a ve-RDF of weight at most l for star convex bipartite graphs, comb convex bipartite graphs, chordal graphs and planar graphs is NP-complete. On the positive side, we show that MVERDP is linear time solvable for threshold graphs, chain graphs and bounded tree-width graphs. On the approximation point of view, a 2-approximation algorithm for MVERDP is presented. It is also shown that vertex cover and vertex-edge Roman domination problems are not equivalent in computational complexity aspects. Finally, an integer linear programming formulation for MVERDP is presented. [ABSTRACT FROM AUTHOR]