Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): Thomas Zaslavsky In descending generality I survey: five partial orderings of graphs, the induced-subgraph ordering, and examples like perfect, threshold, and mock threshold graphs. The emphasis is on how the induced subgraph ordering differs from other popular orderings and leads to different basic questions.

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): Mukti Acharya In this paper, we initiate the study on C-cordial labeling in signed graphs and characterize paths and cycles with given number of negative sections and stars which admit C-cordial labeling.

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): Andreas M. Hinz We list some unsolved problems concerning two meanwhile famous classes of graphs, namely the Hanoi graphs and the Sierpiński graphs. Whereas many graph parameters have been determined and metric properties are well-understood for the latter, the former give rise to notoriously difficult questions, in particular when it comes to distance-related tasks.

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): Tao-Ming Wang, Guang-Hui Zhang An edge-graceful labeling of a finite simple graph with p vertices and q edges is a bijection from the set of edges to the set of integers { 1 , 2 , ⋯ , q } such that the vertex sums are pairwise distinct modulo p, where the vertex sum at a vertex is the sum of labels of all edges incident to such vertex. A graph is called edge-graceful if it admits an edge-graceful labeling. In this article, we verify that an regular graph of odd degree is edge-graceful if it contains either of two particular 3-regular spanning subgraphs, namely, a quasi-prism factor and a claw factor.

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): Thomas Zaslavsky I propose that most problems about circles (cycles, circuits) in ordinary graphs that have odd or even length find their proper setting in the theory of signed graphs, where each edge has a sign, + or −. Even-circle and odd-circle problems correspond to questions about positive and negative circles in signed graphs. (The sign of a circle is the product of its edge signs.) I outline questions about circles in signed graphs, that seem natural and potentially important.

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): Arnfried Kemnitz, Massimiliano Marangio, Margit Voigt A simple graph G = ( V , E ) is called L-colorable if there is a proper coloring c of the vertices with c ( v ) ∈ L ( v ) for all v ∈ V where L ( v ) is an assignment of colors to v. A function f : V → N is called a choice function of G if G is L-colorable for every assignment L with L ( v ) = f ( v ) for all v ∈ V . The sum choice number χ s c ( G ) of G is defined as the minimum of ∑ v ∈ V f ( v ) over all choice functions f of G. In this note we give general lower and upper bounds for the sum choice number. We determine all connected graphs G whose sum choice number attains the lower bound 2 V − 1 or 2 V . Moreover, we determine all complete multipartite graphs whose sum choice number attains the upper bound V + E .

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): T. Asir, T. Tamizh Chelvam The topological properties of graphs are well studied. More specifically the genus of graphs and their embeddings are attractions to many authors. In this survey, we present the results concerning the genus of total graph and generalized the total graph and generalized total graphs of commutative rings.

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): R. Rajkumar, T. Anitha Let S be a semigroup. We define the directed reduced power graph of S, denoted by P → ( S ) , is a digraph with vertex set S, and for u, v ∈ S, there is an arc from u to v if and only if u ≠ v and 〈 v 〉 ⊂ 〈 u 〉 . The (undirected) reduced power graph of S, denoted by P ( S ) , is the underlying graph of P → ( S ) . This means that the set of vertices of P ( S ) is equal to S and two vertices u and v are adjacent if and only if u ≠ v and 〈 v 〉 ⊂ 〈 u 〉 or 〈 u 〉 ⊂ 〈 v 〉 . In this paper, we study some interplay between the algebraic properties of a group and the graph theoretic properties of its (directed and undirected) reduced power graphs. Also we establish some relationship between the reduced power graphs and power graphs of groups.

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): Devendra Lad, P. Venkata Subba Reddy, J. Pavan Kumar Let G = ( V , E ) be a simple, undirected and connected graph. A connected dominating set S ⊆ V ( G ) is a secure connected dominating set of G, if for each u ∈ V ( G ) \ S , there exists v ∈ S such that ( u , v ) ∈ E ( G ) and the set ( S \ { v } ) ∪ { u } is a connected dominating set of G. The minimum cardinality of a secure connected dominating set of G denoted γ s c ( G ) , is called the secure connected domination number of G. In this paper, we show that the decision problems of finding a minimum secure connected dominating set and a minimum secure total dominating set are NP-complete for split graphs. We initiate the study of 2-secure domination and show that the decision problem corresponding to the computation of 2-secure domination number of a graph is NP-complete, even when restricted to split graphs or bipartite graphs. Finally we show that given two positive integers k ( ≥ 2 ) and n ( ≥ max { 4 , k } ) there exists a graph G with V ( G ) = n and γ s c ( G ) = k .

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): Devsi Bantva Let G be a finite, connected, undirected graph with diameter diam(G) and d(u, v) denote the distance between u and v in G. A radio labeling of a graph G is a mapping f : V ( G ) → { 0 , 1 , 2 , … } such that f ( u ) − f ( v ) ≥ diam ( G ) + 1 − d ( u , v ) for every pair of distinct vertices u, v of G. The radio number of G, denoted by rn(G), is the smallest integer k such that G has a radio labeling f with max { f ( v ) : v ∈ V ( G ) } = k . In this paper, we determine the radio number for three families of trees obtained by taking graph operation on a given tree or a family of trees.

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): Devsi Bantva For a connected graph G, let diam(G) and d(u, v) denote the diameter of G and distance between u and v in G. A radio labeling of a graph G is a mapping ϕ : V ( G ) → { 0 , 1 , 2 , … } such that ϕ ( u ) − ϕ ( v ) ≥ diam ( G ) + 1 − d ( u , v ) for every pair of distinct vertices u, v of G. The span of ϕ is defined as span ( ϕ ) = max { ϕ ( u ) − ϕ ( v ) : u , v ∈ V ( G ) } . The radio number rn(G) of G is defined as rn ( G ) = min { span ( ϕ ) : ϕ is a radio labeling of G } . In this paper, we determine the radio number for middle graph of paths.

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): Mahdi Amani We introduce gaps which are special edges or external pointers in AVL trees such that the height difference between the subtrees rooted at two endpoints of a gap is equal to 2. Using gaps we prove the Basic-Theorem which illustrates how the size of an AVL tree (and its subtrees) can be represented by a series of powers of 2 of the heights of the gaps, this theorem is the first such a simple formula to characterize the number of nodes in an AVL tree. Then, we study the extreme case of AVL trees, the perfectly unbalanced AVL trees, by defining Fibonacci-isomorphic trees, and we show that they have the maximum number of gaps in AVL trees. In the rest of the paper, we study combinatorial properties of these trees. Keywords: AVL tree, Fibonacci tree, Fibonacci-isomorphic tree, Gaps in AVL tree, Subtree size, Enumeration, Encoding.

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): Mark Korenblit, Vadim E. Levit The paper investigates relationship between algebraic expressions and graphs. Our intention is to simplify graph expressions and eventually find their shortest representations. We prove the decomposition lemma which asserts that the shortest expression of a subgraph of a graph G is not larger than the shortest expression of G. Using this finding, we estimate an upper bound of a size of the shortest expression for any two-terminal directed acyclic graph.

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): Pankaj Kumar Das Error locating code is a concept that compromise between short and long code length and identifies the corrupted sub-block(s) containing the error occurring within subblock(s). This paper presents bounds on the number of parity check digits of such error-locating codes that are capable of not only detecting any burst error of length b or less within a sub-block, but also can locate several such corrupted sub-blocks. We also provide an example of such a code.

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): Vinod Kumar Mishra, Pankaj Singh Sammal During recent years graphics processing unit (GPU) has become an inexpensive high-performance parallel computing units and general purpose computation on graphics processing unit (GPGPU) become an alternative of conventional CPU computation, which provide massive parallel computation capability to a normal computer over a system which uses only CPU. This paper investigates the performance of the algorithm for the solution of single source shortest path (SSSP) problem, all pair shortest path (APSP) problem and graph coloring problem for large graph on GPU regardless of a specific vendor. The application programming interface (API) used for programming in graphic processing unit is open compute language (OpenCL), it is a specification for heterogeneous computing. The performance of solutions on GPU is compared with the solution on CPU in term of their execution time. The result indicates the significant improvement in the performance of the solutions on GPU over solutions on CPU.

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): Sriparna Chattopadhyay, Pratima Panigrahi The power graph G ( G ) of a finite group G is the graph whose vertices are the elements of G and two distinct vertices are adjacent if and only if one is an integral power of the other. Here we concentrate on sum of powers of the non-zero Laplacian eigenvalues of G ( Z n ) and G ( D n ) . As a result we obtain bounds for Laplacian-energy-like (LEL) invariant of the same graphs.

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): K. Pattabiraman In this paper, the exact formulae for the generalized product degree distance, reciprocal product degree distance and product degree distance of Mycielskian graph and its complement are obtained. Also, we obtain the sharp upper and lower bounds for the sum- connectivity index of Mycielskian graph. (http://www.elsevier.com/locate/endm)

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): H.S. Ramane, S.S. Shinde The degree exponent matrix DE(G) of a graph G is a square matrix whose (i, j)-th entry is d i d j whenever i ≠ j , otherwise it is zero, where d i vertex of G. In this paper we obtain the characteristic polynomial of the degree exponent matrix of graphs obtained by some graph operations.

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): Prabhakar R. Hampiholi, Jotiba P. Kitturkar Semigraph is introduced by E. Sampathkumar as a generalization of a graph. Semigraph G is edge complete if any two edges of G are adjacent. In this paper, we prove the special results on the enumeration of various categories of non-isomorphic edge complete semigraphs.

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): Biswajit Deb Given two vertices u, v in a graph G, by C v u we denote the configuration of G with a robot at vertex u, a hole at vertex v and obstacles at the remaining vertices of G graph G is said to be complete S-reachable if starting from each configurations in G the robot can be taken to any other vertex of G by a sequence of moves consisting of simple moves of the obstacles and mRJ moves of the robot for m ∈ S , where S is a finite non-empty set of non-negative integers. An mRJ move on C v u is the process of moving the robot from u to v by jumping over m obstacles if there is a u-v path of length m + 1 in G. A 0 R J move is known as a simple move. We characterize the biconnected graphs that are complete { m } -reachable, for some positive integer m.

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): Sarifa Khatun, Sk. Md. Abu Nayeem This paper contains some results on graceful labeling of some zero divisor graphs. We prove that the zero divisor graph of Z n , the commutative ring of integers modulo n, is graceful if n = pq or 4p or 9p, where p and q both are prime numbers.

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): A.K. Bhuniya, Sajal Kumar Mukherjee The power graph P (G) of a finite group G is the graph with vertex set G and two distinct vertices are adjacent if either of them is a power of the other. Here we show that the power graph P ( G 1 × G 2 ) of the direct product of two groups G 1 and G 2 is not isomorphic to either of the direct, cartesian and normal product of their power graphs P (G 1) and P (G 2). A new product of graphs, namely generalized product, has been introduced and we prove that the power graph P ( G 1 × G 2 ) is isomorphic to a generalized product of P (G 1) and P (G 2).

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): Arti Pandey, B.S. Panda A set D ⊆ V of a graph G = (V, E) is called a restrained dominating set of G if every vertex not in D is adjacent to a vertex in D and to a vertex in V \ D . The Minimum Restrained Domination problem is to find a restrained dominating set of minimum cardinality. The decision version of the Minimum Restrained Domination problem is known to be NP-complete for chordal graphs. In this paper, we strengthen this NP-completeness result by showing that the problem remains NP-complete for doubly chordal graphs, a subclass of chordal graphs. We also propose a polynomial time algorithm to solve the Minimum Restrained Domination problem in block graphs, a subclass of doubly chordal graphs.

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): K. Raja Chandrasekar, A. Mohammed Abid An edge irredundant coloring of a graph G = (V, E) is an edge partition ∏ = { E 1 , E 2 , … , E k } of E into nonempty edge irredundant sets. The edge irratic number is the minimum order of an edge irredundant coloring of G and it is denoted by χ i r ′ ( G ) . In this paper a study has been initiated on edge irredundant coloring of G. We have characterized all graphs G for which χ i r ′ ( G ) = m or m − 1 , where m is the size of a graph G. Also we have obtained some bounds on χ i r ′ for triangle-free graphs and trees.

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): Sasmita Barik, Gopinath Sahoo Let F, H v be simple connected graphs on n and m+1 vertices, respectively. Let v be a specified vertex of H v and u 1 , … , u k ∈ F . Then the graph G = G [ F , u 1 , … , u k , H v ] obtained by taking one copy of F and k copies of H v , and then attaching the i-th copy of H v to the vertex u i , i = 1 , … , k , at the vertex v of H v (identify u i with the vertex v of the i-th copy) is called a graph with k pockets. In [Barik, S., On the Laplacian spectra of graphs with pockets, Linear and Multilinear Algebra, 56 (2008), 481–490], Barik raised the question that ‘how far can the Laplacian spectrum of G be described by using the Laplacian spectra of F and H v '’ and discussed the case when deg(v) = m in H v . In this article, we study the problem for more general cases and describe the Laplacian spectrum. As an application, we construct new nonisomorphic Laplacian cospectral graphs from the known ones.

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): H.P. Patil, V. Raja The purpose of this paper is to introduce the wheel-trees, which are the natural extensions of 4-trees studied in [Beineke L. W and Pippert R. E., Properties and characterizations of k-trees, Mathematica., 18, (1971), 141–151; Patil H. P., On the structure of k-trees, J. Comb. Inform & System Sci., 11 (2–4), (1986), 57–64] and also establish the properties and characterizations of the wheel-trees G 〈 W k 〉 for k ≥ 6 . Moreover, the chromatic number, centrality, domination and Roman domination numbers of the wheel-trees of order ≥6 are determined.

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): Mahipal Jadeja, Rahul Muthu, V. Sunitha Given a set of nonempty subsets of some universal set, their intersection graph is defined as the graph with one vertex for each set and two vertices are adjacent precisely when their representing sets have non-empty intersection. Sometimes these sets are finite, but in many well known examples like geometric graphs (including interval graphs) they are infinite. One can also study the reverse problem of expressing the vertices of a given graph as distinct sets in such a way that adjacency coincides with intersection of the corresponding sets. The sets are usually required to conform to some template, depending on the problem, to be either a finite set, or some geometric set like intervals, circles, discs, cubes etc. The problem of representing a graph as an intersection graph of sets was first introduced by Erdos [Alon, Noga, Covering graphs by the minimum number of equivalence relations, Combinatorica 6(1986), 201–206] and they looked at minimising the underlying universal set necessary to represent any given graph. In that paper it was shown that the problem is NP complete. In this paper we study a natural variant of this problem which is to consider graphs where vertices represent distinct sets and adjacency coincides with disjointness. Although this is nearly the same problem on the complement graph, for specific families of graphs this is a more natural way of viewing it. The parameter we take into account is the minimum universe size possible (disregarding individual label sizes).

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): K. Pattabiraman, M. Vijayaragavan The edge a-Zagreb index and its coindex are defined as Z a ( G ) = ∑ u v ∈ E ( G ) ( d a ( u ) + d ( v ) ) and Z ‾ a ( G ) = ∑ u v ∉ E ( G ) ( d a ( u ) + d a ( v ) ) . In this paper, we obtain the exact expressions for the edge a-Zagreb indices and its coindices of two different transformation of graphs and their complements. Using the results obtained here, the value of F-index and its coindex for above transformation graphs are obtained.

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): Meenakshi Wasadikar, Amit Dabhole In this paper, we study the incomparability graph of the lattices L n and L n 1 2 . I such graphs, we find minimum dominating set and order of a graph. We express the cardinality of neighbourhood of an atom by a binomial expression.

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): Angshu Kumar Sinha, Akul Rana, Anita Pal Let G = ( V , E ) be an undirected graph with vertex set V and edge set E. The open neighborhood N(e) of an edge e ∈ E is the set of all edges adjacent to e. The closed neighborhood of e is denoted by N[e] and N [ e ] = N ( e ) ∪ { e } . A function f : E → { 1 , − 1 } is said to be a signed edge dominating function (SEDF), if f satisfies the condition ∑ e ′ ∈ N [ e ] f ( e ′ ) ≥ 1 for every e ∈ E . The minimum of the values of ∑ e ∈ E f ( e ) , taken over all signed edge dominating functions f on G, is called the signed edge domination number (SEDN) of G and is denoted by γ s ′ ( G ) . In this paper, an O ( n 2 ) time algorithm is designed to compute the signed edge domination number of interval graphs.

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): Sunil Kumar R., Kannan Balakrishnan Betweenness centrality is a widely used to measure the potential of a node to control the communication over the network. It measures the extent to which a vertex is part of the shortest paths between pairs of other vertices in a graph. In this paper, we establish expression for betweenness centrality in Cartesian product of graphs. And investigate the same on certain graphs such as Hamming graphs, hypercubes, Cartesian product of path and cycle.

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): Sunil Kumar R., Kannan Balakrishnan For each n and k ( n > 2 k ) , the generalized Petersen graph GP (n, k) is a trivalent graph with vertex set { u i , v i 0 ≤ i ≤ n − 1 } and edge set { u i u i + 1 , u i v i , v i v i + k 0 ≤ i ≤ n − 1 , subscripts reduced modulo n } . There are three kinds of edges – outer edges, spokes and inner edges. Outer vertices generate an n-cycle called outer cycle and the inner vertices generate one or more cycles called inner cycles. In this paper, we consider the number of shortest paths or geodesics between two vertices of GP (n, 2).

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): Ruhul Amin, Sk. Md. Abu Nayeem The F-coindex of a graph G is a very recently introduced topological index, and it is defined as the sum of the square of the degrees of every pair of non-adjacent vertices. In this paper, we determine the extremal trees with minimum, second minimum and third minimum F-coindex.

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): Aloysius Godinho, T. Singh Let G = (V, E) be a graph of order n. A bijective function f : V → { 1 , 2 , … , n } is said to be a distance magic labeling of G if for every v ∈ V , ∑ x ∈ N ( v ) f ( x ) = k (a constant). A graph which admits such a labeling is said to be a distance magic graph. In this paper we study distance magic labeling for the neighborhood expansion D p ( G ) of a graph G and present a method for embedding regular graphs into distance magic graphs.

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): A.K. Handa, Aloysius Godinho, T. Singh Let G be a graph of order n. Let f : V ( G ) → { 1 , 2 , … , n } be a bijection. The weight w f ( v ) of a vertex with respect to f is defined by w f ( v ) = ∑ x ∈ N ( v ) f ( x ) . The labeling f is said to be distance antimagic if w f ( u ) ≠ w f ( v ) for every pair of vertices u , v ∈ V ( G ) . If the graph G admits such a labeling then G is said to be a distance antimagic graph. In this paper we investigate the existence of distance antimagic labeling in the ladder graph L n ≅ P 2 □ P n .

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): Deepa Sinha, Anshu Sethi A signed graph (also known as sigraph) S is a graph G ′ where every edge y have value s ′ ( y ) ∈ { − 1 , + 1 } known as its sign function and is denoted as S = ( G ′ , s ′ ) . Given a sigraph S = ( V , E , σ ) , for every vertex v ∈ V ( S ) , take a new vertex v ′ . Join v ′ to all vertices of S adjacent to v such that, σ Λ ( u v ′ ) = σ ( u v ) , u ∈ N ( v ) . The sigraph Λ ( S ) = ( V Λ , E Λ , σ Λ ) thus produced is called the splitting sigraph of S. Here we define an algorithm to produce a splitting sigraph and root splitting sigraph from a given sigraph, if it exists, in O ( n 4 ) steps.

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): Priyanka Singh, Pratima Panigrahi A simple connected graph G is said to be a self-centered graph if every vertex has the same eccentricity. Tensor product of self-centered graphs may not be a self-centered graph. In this paper we study self-centeredness property of tensor product of cycles with themselves and other graphs, complete graphs with themselvesand other self-centered graphs, wheel graphs with themselves and other self-centered graphs, and square of cycles with themselves.

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): Nibedita Mandal, Pratima Panigrahi An L ( 2 , 1 ) -coloring(or labeling) of a 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 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 assigned by it. The span of a graph G, denoted by λ ( G ) , is the smallest positive integer λ such that there is an L ( 2 , 1 ) coloring of G using colors from { 0 , ⋯ , λ } . A no-hole coloring is defined to be an L ( 2 , 1 ) -coloring of a graph with span k which uses all the colors from { 0 , 1 , ⋯ , k } for some integer k not necessarily the span of the graph. An L ( 2 , 1 ) -coloring is defined as irreducible if color of none of the vertices can be decreased and yield another L ( 2 , 1 ) -coloring of the same graph. An irreducible no-hole coloring of a graph G, in short inh-coloring of G, is an L ( 2 , 1 ) -coloring of G which is both irreducible and no-hole. The lower inh-span or simply inh-span of a graph G, denoted by λ i n h ( G ) , is the smallest integer k such that there exists an inh-coloring of G with span k. In this paper we work on the L ( 2 , 1 ) -coloring and inh-coloring of the Cartesian product K m □ C n of complete graphs and cycles and find the exact values of λ ( K m □ C n ) and λ i n h ( K m □ C n ) for some values of m and n, and give upper bounds to the same in the remaining cases. We also give two upper bounds of the span of the Cartesian product of two arbitrary graphs which are better than the upper bound of Shao and Yeh [Sha... PubDate: 2017-12-13T09:16:42Z

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): Pallavi Jain, Gur Saran, Kamal Srivastava Vertex Separation Minimization Problem (VSMP) consists of finding a layout of a graph G = (V, E) which minimizes the maximum vertex cut or separation of a layout. It is an NP-complete problem in general for which metaheuristic techniques can be applied to find near optimal solution. VSMP has applications in VLSI design, graph drawing and computer language compiler design. VSMP is polynomially solvable for grids, trees, permutation graphs and cographs. Construction heuristics play a very important role in the metaheuristic techniques as they are responsible for generating initial solutions which lead to fast convergence. In this paper, we have proposed three construction heuristics H1, H2 and H3 and performed experiments on Grids, Small graphs, Trees and Harwell Boeing graphs, totaling 248 instances of graphs. Experiments reveal that H1, H2 and H3 are able to achieve best results for 88.71%, 43.5% and 37.1% of the total instances respectively while the best construction heuristic in the literature achieves the best solution for 39.9% of the total instances. We have also compared the results with the state-of-the-art meta-heuristic GVNS and observed that the proposed construction heuristics improves the results for some of the input instances. It was found that GVNS obtained best results for 82.9% instances of all input instances and the heuristic H1 obtained best results for 82.3% of all input instances.

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): Jessie Abraham, Micheal Arockiaraj A graph embedding is an important aspect in establishing equivalence of interconnections in parallel and distributed machines. Finding the minimum layout serves as a cost criterion for evaluating a good embedding. The binary hypercube is one of the most widely used topology for interconnection networks due to its simple, deadlock-free routing and broadcasting properties. The locally twisted cube is an important variant of the hypercube with the same number of vertices and connections but exhibits enhanced properties than its counterpart. In this paper we consider the problem of embedding an n-dimensional locally twisted cube into the extended rooted theta mesh in such a way as to minimize its layout.

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): Yogita Singh Kardam, Kamal Srivastava, Reeti Sharma The profile minimization problem is a graph layout problem that consists of finding a linear arrangement (labeling) of vertices of a graph such that the sum of profiles of all vertices is minimum. The profile of a vertex can be defined as the difference of the position of its left most neighbor and the position of that vertex in the linear arrangement. It is an NP-complete problem with applications in the areas where the reordering of rows and columns of a sparse matrix is required in order to reduce the storage space. In this work, we propose a hybrid simulated annealing algorithm with the aim of profile reduction of a given graph by incorporating spectral sequencing for generating the initial solution. Experiments conducted on some benchmark graphs show that our algorithm outperforms the best existing algorithm in some cases and is comparable for rest of the instances. It also attains the optimal values for some classes of graphs with known optimal results.

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): Mukti Acharya, Pranjali, Atul Gaur, Amit Kumar A signed total graph is an ordered pair T Σ ( Γ ( R ) ) : = ( T ( Γ ( R ) ) , σ ) , where T ( Γ ( R ) ) is the total graph of a commutative ring R, called the underlying graph of T Σ ( Γ ( R ) ) and T Σ ( Γ ( R ) ) is associated with a signing of its edges (a, b) by the function σ such that σ ( a , b ) is ‘+’ if a ∈ Z ( R ) or b ∈ Z ( R ) and ‘−’ otherwise. The aim of this paper is to gain a deeper insight into the notion of signed total graph by characterizing the rings for which line signed graph L ( T Σ ( Γ ( R ) ) ) of signed total graph are C-consistent, T Σ ( Γ ( R ) ) -consistent and sign-compatible.

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): Y.S. Gaidhani, C.M. Deshpande, B.P. Athawale Semigraph was defined by Sampathkumar as a generalization of a graph. In this paper the adjacency matrix which represents semigraph uniquely and a characterization of such a matrix is obtained. An algorithm to construct the semigraph from a given square matrix, if semigraphical is given. Some properties of adjacency matrix of semigraph are studied. A sufficient condition for eigen values to be real is also obtained.

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): P.C. Lisna, M.S. Sunitha A b-coloring of a graph G is a proper coloring of the vertices of G such that there exist a vertex in each color class joined to at least one vertex in each other color classes. The b-chromatic number of a graph G, denoted by ϕ ( G ) , is the largest integer k such that G has a b-coloring with k colors. The b-chromatic sum of a graph G(V, E), denoted by ϕ ′ ( G ) is defined as the minimum of sum of colors c(v) of v for all v ∈ V in a b-coloring of G using ϕ ( G ) colors, where the colors are taken as the positive integer. In this paper, the b-chromatic sum of Mycielskian of a path is discussed.

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): Sameeha Rehmani, M.S. Sunitha The concept of Minimum geodetic subgraphs in Graph theory was introduced by G. Chartrand, F. Harary and P. Zhang in 2001. In this paper,the idea is extended to fuzzy graphs using geodesic distance.An upper and lower bound for geodesic number of fuzzy graphs is obtained using which it is established that the geodesic number of a fuzzy graph exceeds or is equal to that of its minimum geodetic fuzzy subgraph. A necessary condition for the geodesic number of a fuzzy graph to be 2 depending on the nodes of its minimum geodetic fuzzy subgraph is obtained and a study on the minimum geodetic fuzzy subgraph of a fuzzy tree is conducted.

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): Deepa Sinha, Ayushi Dhama A signed graph S is a graph in which every edge receive either ‘+’ or ‘-’ called the signs of the edges. The unitary Cayley graph X n is a graph with vertex set Z n , the integers modulo n, where n is a positive integer greater than 1. Two vertices x 1 and x 2 are adjacent in the unitary Cayley graph if and only if their difference is in U n , where U n denotes set of all units of the ring Z n . The properties of balancing and clusterability of unitary Cayley meet signed graph S n ∧ are discussed. Apart from this, the canonically consistency of S n ∧ is determined when n has at most two distinct odd prime factors. Sign-compatibility has been worked out for these graphs as well.

Abstract: Publication date: December 2017 Source:Electronic Notes in Discrete Mathematics, Volume 63 Author(s): A.T. Shahida, M.S. Sunitha For a graph G = (V, E), a set W ⊂ V is a resolving set if for each pair of distinct vertices v 1 , v 2 ∈ V there is a vertex w ∈ W such that d ( v 1 , w ) ≠ d ( v 2 , w ) . A minimum resolving set or basis for G is a resolving set containing a minimum number of vertices and the cardinality of a minimum resolving set is called the metric dimension of G and is denoted by dim(G). In this paper, we investigates the metric dimension of K n + O p , P n + O p and K 1 , n + O p , where O p denotes the empty (isolated) graph of order p.