Authors:K. Kayathri; J. Sakila Devi Pages: 48 - 53 Abstract: Publication date: April 2017 Source:AKCE International Journal of Graphs and Combinatorics, Volume 14, Issue 1 Author(s): K. Kayathri, J. Sakila Devi In this paper, we study the size of edge chromatic 5-critical graphs in several classes of 5-critical graphs. In most of the classes of 5-critical graphs in this paper, we have obtained their exact size and in the other classes of 5-critical graphs, we give new bounds on their number of major vertices and size.

Authors:S.N. Daoud Abstract: Publication date: Available online 24 April 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): S.N. Daoud Solairaju and Chithra introduced a new type of labeling of a graph G with p vertices and q edges called an edge odd graceful labeling if there is a bijection f from the edges of the graph to the set { 1 , 3 , … , 2 q − 1 } such that, when each vertex is assigned the sum of all edges incident to it m o d 2 k , where k = max ( p , q ) , the resulting vertex labels are distinct. In this paper we proved necessary and sufficient conditions for some path and cycle related graphs to be edge odd graceful such as: Friendship graphs, Wheel graph, Helm graph, Web graph, Double wheel graph, Gear graph, Fan graph, Double fan graph and Polar grid graph.

Authors:Richard Behr Abstract: Publication date: Available online 12 April 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Richard Behr We examine the conditions under which a signed graph contains an edge or a vertex that is contained in a unique negative circle or a unique positive circle. For an edge in a unique signed circle, the positive and negative case require the same structure on the underlying graph, but the requirements on the signature are different. We characterize the structure of the underlying graph necessary to support such an edge in terms of bridges of a circle. We then use the results from the edge version of the problem to help solve the vertex version.

Authors:M. Javaid; Masood Ur Rehman Abstract: Publication date: Available online 12 April 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): M. Javaid, Masood Ur Rehman For a graph Γ the algebraic connectivity denoted by a ( Γ ) , is the second smallest eigenvalue of the Laplacian matrix of Γ . In Jiang et al. (2015), proved a unique graph with first minimum algebraic connectivity among the graphs which belong to a class of graphs whose complements are trees. In this paper, we characterize the unique graph with second minimum algebraic connectivity in the same aforesaid class of graphs.

Authors:H. Abdollahzadeh Ahangar; M. Najimi; V. Samodivkin; Ismael G. Yero Abstract: Publication date: Available online 11 April 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): H. Abdollahzadeh Ahangar, M. Najimi, V. Samodivkin, Ismael G. Yero Given two vertices u and v of a nontrivial connected graph G , the set I [ u , v ] consists all vertices lying on some u − v geodesic in G , including u and v . For S ⊆ V ( G ) , the set I [ S ] is the union of all sets I [ u , v ] for u , v ∈ S . A set S ⊆ V ( G ) is a total restrained geodetic set of G if I [ S ] = V ( G ) and the subgraphs induced by S and V ( G ) − S have no isolated vertex. The minimum cardinality of a total restrained geodetic set of G is the total restrained geodetic number g t r ( G ) of G and a total restrained geodetic set of G whose cardinality equals g t r ( G ) is a minimum total restrained geodetic set of G . A subset T of a minimum total restrained geodetic set S is a forcing subset for S if S is the unique minimum total restrained geodetic set of G containing T . The forcing total restrained geodetic number f t r ( S ) of S is the minimum cardinality of a forcing subset of S and the forcing total restrained geodetic number f t r ( G ) of G is the minimum forcing total restrained geodetic number among all minimum total restrained geodetic sets of G . In this article we determine all pairs a , b of integers such that f t r ( G ) = a and PubDate: 2017-04-19T14:59:29Z DOI: 10.1016/j.akcej.2017.03.007

Authors:Johnathan Barnett; Adam Blumenthal; Peter Johnson; Cadavious Jones; Ryan Matzke; Egbert Mujuni Abstract: Publication date: Available online 31 March 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Johnathan Barnett, Adam Blumenthal, Peter Johnson, Cadavious Jones, Ryan Matzke, Egbert Mujuni For any (finite simple) graph G the secure domination number of G satisfies γ s ( G ) ≥ V ( G ) 2 . Here we find a secure-dominating set S in G such that S = ⌈ V ( G ) 2 ⌉ in all cases when G is a grid, and in the majority of cases when G is a cylindrical or toroidal grid. In all such cases, S satisfies the additional requirement that G [ S ] is connected. We make note that the concept of secure-dominating sets considered in this paper is quite different from the other secure domination currently of interest. 1 1 The other sort of secure domination: A dominating set S ⊆ V ( G ) is secure dominating (in G) if and only if for every v ∈ V ( G ) ∖ S there is some u ∈ S such that ( S ∖ { u } ) ∪ { v } is dominating, in G.

Authors:Sk Amanathulla; Madhumangal Pal Abstract: Publication date: Available online 23 March 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Sk Amanathulla, Madhumangal Pal For a given graph G = ( V , E ) , the L ( 3 , 2 , 1 ) - and L ( 4 , 3 , 2 , 1 ) -labeling problems assign the labels to the vertices of G . Let Z ∗ be the set of non-negative integers. An L ( 3 , 2 , 1 ) - and L ( 4 , 3 , 2 , 1 ) -labeling of a graph G is a function f : V → Z ∗ such that f ( x ) − f ( y ) ≥ k − d ( x , y ) , for k = 4 , 5 respectively, where d ( x , y ) represents the distance (minimum number of edges) between the vertices x and y , and 1 ≤ d ( x , y ) ≤ k − 1 . The L ( 3 , 2 , 1 ) - and L ( 4 , 3 , 2 , 1 ) -labeling numbers of a graph G , are denoted by λ 3 , 2 , 1 ( G ) and λ 4 , 3 , 2 , 1 ( G ) and they are the difference between highest and lowest labels used in L ( 3 , 2 , 1 ) - and L ( 4 , 3 , 2 , 1 ) -labeling respectively. In this paper, for an interval graph G , it is shown that λ 3 , 2 , 1 ( G ) ≤ 6 Δ − 3 and λ 4 , 3 , 2 , 1 ( G ) ≤ 10 Δ − 6 , where Δ represents the maximum degree of the vertices of G . Also, two algorithms are designed to label an interval graph by maintaining L ( 3 , 2 , 1 ) - and L ( 4 , 3 , 2 , 1 ) -labeling conditio... PubDate: 2017-03-28T21:45:39Z DOI: 10.1016/j.akcej.2017.03.002

Authors:S. Kavitha; R. Kala Abstract: Publication date: Available online 22 February 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): S. Kavitha, R. Kala Let R be a commutative ring with non-zero identity. The cozero-divisor graph of R , denoted by Γ ′ ( R ) , is a graph with vertex-set W ∗ ( R ) , which is the set of all non-zero non-unit elements of R , and two distinct vertices x and y in W ∗ ( R ) are adjacent if and only if x ∉ R y and y ∉ R x , where for z ∈ R , R z is the ideal generated by z . In this paper, we determine all isomorphism classes of finite commutative rings R with identity whose Γ ′ ( R ) has genus one. Also we characterize all non-local rings for which the reduced cozero-divisor graph Γ r ( R ) is planar.

Authors:M. Javaid; A.A. Bhatti; M.K. Aslam Abstract: Publication date: Available online 21 February 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): M. Javaid, A.A. Bhatti, M.K. Aslam A graph labeling is a mapping that assigns numbers to graph elements. The domain can be the set of all vertices, the set of all edges or the set of all vertices and edges. A labeling in which domain is the set of vertices and edges is called a total labeling. For a graph G with the vertex set V ( G ) and the edge set E ( G ) , a total labeling f : V ( G ) ∪ E ( G ) → { 1 , 2 , 3 , … , V ( G ) + E ( G ) } is called an ( a , d ) -edge antimagic total labeling if the set of edge weights { f ( x ) + f ( x y ) + f ( y ) : x y ∈ E ( G ) } forms an arithmetic progression with initial term a and common difference d . An ( a , d ) -edge antimagic total labeling is called a super ( a , d ) -edge antimagic total labeling if the smallest labels are assigned to the vertices. In this paper, we investigate the super ( a , d ) -edge-antimagic total labeling of a subclass of trees called subdivided stars for all possible values of d , mainly d = 1 , 3 .

Abstract: Publication date: Available online 21 February 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Rocío Sánchez-López Let D be a digraph, possibly infinite, V( D ) and A( D ) will denote the sets of vertices and arcs of D , respectively. A subset K of V( D ) is said to be a kernel if it is both independent (a vertex in K has no successor in K ) and absorbing (a vertex not in K has a successor in K ). An infinite digraph D is said to be a finitely critical kernel imperfect digraph if D contains no kernel but every finite induced subdigraph of D contains a kernel. In this paper we will characterize the infinite kernel perfect digraphs by means of finitely critical imperfect digraphs and strong components of its asymmetric part and then, by using some previous theorems for infinite digraphs, we will deduce several results from the main result. Richardson’s theorem establishes that if D is a finite digraph without cycles of odd length, then D has a kernel. In this paper we will show a generalization of this theorem for infinite digraphs.

Authors:Ali Ahmad; Martin Maria Naseem Andrea Abstract: Publication date: Available online 21 February 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Ali Ahmad, Martin Bača, Maria Naseem, Andrea Semaničová-Feňovčíková For a graph G = ( V ( G ) , E ( G ) ) , an edge labeling φ : E ( G ) → { 0 , 1 , … , k − 1 } where k is an integer, 2 ≤ k ≤ E ( G ) , induces a vertex labeling φ ∗ : V ( G ) → { 0 , 1 , … , k − 1 } defined by φ ∗ ( v ) = φ ( e 1 ) ⋅ φ ( e 2 ) ⋅ … ⋅ φ ( e n ) ( mod k ) , where e 1 , e 2 , … , e n are the edges incident to the vertex v . The function φ is called a k -total edge product cordial labeling of G if ( e φ ( i ) + v φ ∗ ( i ) ) − ( e φ ( j ) + v φ ∗ ( j ) ) ≤ 1 for every i , j , 0 ≤ i < j ≤ k − 1 , where e φ ( i ) and v φ ∗ ( i ) are the number of edges e and vertices v with φ ( e ) = i and φ ∗ ( v ) = i , respectively. In this paper, we investigate the existence of 3 -total edge product cordial labeling of hexagonal grid.

Authors:Pradeep G. Bhat; Sabitha D’Souza Abstract: Publication date: Available online 17 February 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Pradeep G. Bhat, Sabitha D’Souza In this paper, we introduce the new concept of color Signless Laplacian energy L E c + ( G ) . It depends on the underlying graph G and the colors of the vertices. Moreover, we compute color signless Laplacian spectrum and the color signless Laplacian energy of families of graph with the minimum number of colors. The color signless Laplacian energy for the complement of some colored graphs is also obtained.

Authors:Christian Rubio-Montiel Abstract: Publication date: Available online 16 February 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Christian Rubio-Montiel A graph is chordal if every induced cycle has three vertices. The Hadwiger number is the order of the largest complete minor of a graph. We characterize the chordal graphs in terms of the Hadwiger number and we also characterize the families of graphs such that for each induced subgraph H , (1) the Hadwiger number of H is equal to the maximum clique order of H , (2) the Hadwiger number of H is equal to the achromatic number of H , (3) the b -chromatic number is equal to the pseudoachromatic number, (4) the pseudo- b -chromatic number is equal to the pseudoachromatic number, (5) the Hadwiger number of H is equal to the Grundy number of H , and (6) the b -chromatic number is equal to the pseudo-Grundy number.

Authors:Raweerote Suparatulatorn; Suthep Suantai; Watcharaporn Cholamjiak Abstract: Publication date: Available online 15 February 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Raweerote Suparatulatorn, Suthep Suantai, Watcharaporn Cholamjiak In this paper, we prove a strong convergence theorem for two different hybrid methods by using CQ method for a finite family of G-nonexpansive mappings in a Hilbert space. We give an example and numerical results for supporting our main results and compare the rate of convergence of the two iterative methods.

Authors:Sethuraman Ragukumar Abstract: Publication date: Available online 14 February 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): G. Sethuraman, P. Ragukumar Inspired by the method of Koh et al. (1979) of combining known graceful trees to construct bigger graceful trees, a new class of graceful trees is constructed from a set of k known graceful trees, k ≥ 2 in a specific way. In fact, each member of this new class of trees admits α -labeling, a stronger version of graceful labeling. Consequently, each member of this family of trees decomposes complete graphs and complete bipartite graphs.

Authors:Harishchandra S. Ramane; Vinayak V. Manjalapur; Ivan Gutman Abstract: Publication date: Available online 12 February 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Harishchandra S. Ramane, Vinayak V. Manjalapur, Ivan Gutman The general sum-connectivity index, general product-connectivity index, general Zagreb index and coindices of line graphs of subdivision graphs of tadpole graphs, wheels and ladders have been reported in the literature. In this paper, we obtain general expressions for these topological indices for the line graph of the subdivision graphs, thus generalizing the existing results.

Authors:Nader Jafari Rad Abstract: Publication date: Available online 6 February 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Nader Jafari Rad A subset S of vertices of a graph G is a dominating set of G if every vertex in V ( G ) − S has a neighbor in S . The domination number γ ( G ) is the minimum cardinality of a dominating set of G . A dominating set S is an isolate dominating set if the induced subgraph G [ S ] has at least one isolated vertex. The isolate domination number γ 0 ( G ) is the minimum cardinality of an isolate dominating set of G . In this paper we study the complexity of the isolate domination in graphs, and obtain several bounds and characterizations on the isolate domination number, thus answering some open problems.

Authors:Shehnaz Akhter; Muhammad Imran Abstract: Publication date: Available online 29 December 2016 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Shehnaz Akhter, Muhammad Imran For a (molecular) graph, the first Zagreb index M 1 is equal to the sum of squares of the degrees of vertices, and the second Zagreb index M 2 is equal to the sum of the products of the degrees of pairs of adjacent vertices. The F -index of a graph G denoted by F ( G ) or M 3 ( G ) is defined as the sum of cubes of the degrees of vertices of the graph. The total π -electron energy depends on the degree based sum M 1 ( G ) = ∑ v ∈ V deg G ( v ) 2 and F ( G ) = ∑ v ∈ V deg G ( v ) 3 , it was shown in the study of structure-dependency of total π -electron energy in 1972. The first index was named first Zagreb index and the second sum ∑ v ∈ V deg G ( v ) 3 has been never further studied. Recently, this sum was named Forgotten index or the F-index by Furtula and Gutman and it was shown to have an exceptional applicative potential. The first and second Zagreb indices for the four operations on graphs were studied by Deng et al. (2016). In this paper, we extend this study to the F -index of graphs and determine the closed formulas for the F -index of four operations on graphs.

Authors:Shibsankar Das; Kalpesh Kapoor Abstract: Publication date: Available online 29 December 2016 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Shibsankar Das, Kalpesh Kapoor We consider the problem of finding a bijection to match a pattern in a text where both the pattern and the text are strings from distinct alphabets. The objective of weighted approximate parameterized string matching problem is to find approximate parameterized pattern of length m match under weighted Hamming distance in a text of length n . Our main result is an O ( n m ) time algorithm for this problem. We also investigate string comparison problem with k threshold under weighted Hamming distance and give a O ( m + k ) time solution. All the above time complexities assume constant size alphabets.

Authors:Emily Chizmar; Colton Magnant; Pouria Salehi Nowbandegani Pages: 103 - 106 Abstract: Publication date: Available online 25 June 2016 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Emily Chizmar, Colton Magnant, Pouria Salehi Nowbandegani This note introduces the vertex proper connection number of a graph and provides a relationship to the chromatic number of minimally connected subgraphs. Also a notion of total proper connection is introduced and a question is asked about a possible relationship between the total proper connection number and the vertex and edge proper connection numbers.

Authors:Gee-Choon Lau; Zhen-Bin Gao; Sin-Min Lee; Guang-Yi Sun Pages: 107 - 111 Abstract: Publication date: Available online 15 July 2016 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Gee-Choon Lau, Zhen-Bin Gao, Sin-Min Lee, Guang-Yi Sun Let G be a graph with vertex set V ( G ) and edge set E ( G ) . A vertex labeling f : V ( G ) → Z 2 induces an edge labeling f + : E ( G ) → Z 2 defined by f + ( x y ) = f ( x ) + f ( y ) , for each edge x y ∈ E ( G ) . For i ∈ Z 2 , let v f ( i ) = { v ∈ V ( G ) : f ( v ) = i } and e f ( i ) = { e ∈ E ( G ) : f + ( e ) = i } . We say f is friendly if v f ( 0 ) − v f ( 1 ) ≤ 1 . We say G is cordial if e f ( 1 ) − e f ( 0 ) ≤ 1 for a friendly labeling f . The set F I ( G ) = { e f ( 1 ) − e f ( 0 ) : f is friendly } is called the friendly index set of G . In this paper, we investigate the friendly index sets of the edge-gluing of a complete graph K n and n copies of cycles C 3 . The cordiality of the graphs is also determined.

Authors:Muhammad Imran; Hafiz Usman Afzal; A.Q. Baig Pages: 112 - 119 Abstract: Publication date: Available online 23 June 2016 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Muhammad Imran, Hafiz Usman Afzal, A.Q. Baig Let G = ( V , E ) be a finite, simple and undirected graph of order p and size q . A super edge-magic total labeling of a graph G is a bijection λ : V ( G ) ∪ E ( G ) → { 1 , 2 , … , p + q } , where the vertices are labeled with the numbers 1 , 2 , … , p and there exists a constant t such that f ( x ) + f ( x y ) + f ( y ) = t , for every edge x y ∈ E ( G ) . The super edge-magic deficiency of a graph G , denoted by μ s ( G ) , is the minimum nonnegative integer n such that G ∪ n K 1 has a super edge-magic total labeling, or it is ∞ if there exists no such n . In this paper, we are dealing with the super edge-magic deficiency of volvox and dumbbell type graphs.

Authors:Md. Rezaul Karim; Md. Jawaherul Alam; Md. Saidur Rahman Pages: 130 - 139 Abstract: Publication date: Available online 29 June 2016 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Md. Rezaul Karim, Md. Jawaherul Alam, Md. Saidur Rahman The class of doughnut graphs is a subclass of 5-connected planar graphs. It is known that a doughnut graph admits a straight-line grid drawing with linear area, the outerplanarity of a doughnut graph is 3, and a doughnut graph is k -partitionable. In this paper we show that a doughnut graph exhibits a recursive structure. We also give an efficient algorithm for finding a shortest path between any pair of vertices in a doughnut graph. We also propose a nice application of a doughnut graph based on its properties.

Authors:Vladimir Samodivkin Pages: 140 - 145 Abstract: Publication date: Available online 6 July 2016 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Vladimir Samodivkin In this paper we give tight upper bounds on the total domination number, the weakly connected domination number and the connected domination number of a graph in terms of order and Euler characteristic. We also present upper bounds for the restrained bondage number, the total restrained bondage number and the restricted edge connectivity of graphs in terms of the orientable/nonorientable genus and maximum degree.

Authors:N. Paramaguru; R. Sampathkumar Pages: 146 - 156 Abstract: Publication date: Available online 29 June 2016 Source:AKCE International Journal of Graphs and Combinatorics Author(s): N. Paramaguru, R. Sampathkumar For a connected graph G of order V ( G ) ≥ 3 and a k -edge-weighting c : E ( G ) → { 1 , 2 , … , k } of the edges of G , the code, c o d e c ( v ) , of a vertex v of G is the ordered k -tuple ( ℓ 1 , ℓ 2 , … , ℓ k ) , where ℓ i is the number of edges incident with v that are weighted i . (i) The k -edge-weighting c is detectable if every two adjacent vertices of G have distinct codes. The minimum positive integer k for which G has a detectable k -edge-weighting is the detectable chromatic number d e t ( G ) of G . (ii) The k -edge-weighting c is a vertex-coloring if every two adjacent vertices u , v of G with codes c o d e c ( u ) = ( ℓ 1 , ℓ 2 , … , ℓ k ) and c o d e c ( v ) = ( ℓ 1 ′ , ℓ 2 ′ , … , ℓ k ′ ) have 1 ℓ 1 + 2 ℓ 2 + ⋯ + k ℓ k ≠ 1 ℓ 1 ′ + 2 ℓ 2 ′ + ⋯ + k ℓ k ′ . The minimum positive integer PubDate: 2016-07-04T18:41:06Z DOI: 10.1016/j.akcej.2016.06.008

Authors:H. Abdollahzadeh Ahangar; J. Amjadi; S.M. Sheikholeslami; D. Kuziak Pages: 157 - 164 Abstract: Publication date: Available online 1 July 2016 Source:AKCE International Journal of Graphs and Combinatorics Author(s): H. Abdollahzadeh Ahangar, J. Amjadi, S.M. Sheikholeslami, D. Kuziak A 2-rainbow dominating function (2RDF) of a graph G is a function f from the vertex set V ( G ) to the set of all subsets of the set { 1 , 2 } such that for any vertex v ∈ V ( G ) with f ( v ) = 0̸ the condition ⋃ u ∈ N ( v ) f ( u ) = { 1 , 2 } is fulfilled, where N ( v ) is the open neighborhood of v . A maximal 2-rainbow dominating function on a graph G is a 2-rainbow dominating function f such that the set { w ∈ V ( G ) f ( w ) = 0̸ } is not a dominating set of G . The weight of a maximal 2RDF f is the value ω ( f ) = ∑ v ∈ V f ( v ) . The maximal 2-rainbow domination number of a graph G , denoted by γ m r ( G ) , is the minimum weight of a maximal 2RDF of G . In this paper we initiate the study of maximal 2-rainbow domination number in graphs. We first show that the decision problem is NP-complete even when restricted to bipartite or chordal graphs, and then, we present some sharp bounds for γ m r ( G ) . In addition, we determine the maximal rainbow domination number of some graphs.

Authors:Steven Klee; Hunter Lehmann; Andrew Park Pages: 165 - 176 Abstract: Publication date: Available online 17 May 2016 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Steven Klee, Hunter Lehmann, Andrew Park A graph on n vertices is said to admit a prime labeling if we can label its vertices with the first n natural numbers such that any two adjacent vertices have relatively prime labels. Here we extend the idea of prime labeling to the Gaussian integers, which are the complex numbers whose real and imaginary parts are both integers. We begin by defining an order on the Gaussian integers that lie in the first quadrant. Using this ordering, we show that several families of trees admit a prime labeling with the Gaussian integers.

Authors:Jay Bagga; Lowell Beineke; Badri Varma Pages: 177 - 190 Abstract: Publication date: Available online 11 June 2016 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Jay Bagga, Lowell Beineke, Badri Varma In Bagga et al. (1995) a generalization of the line graph concept was introduced. Given a graph G with at least r edges, the super line graph of index r , L r ( G ) , has as its vertices the sets of r edges of G , with two adjacent if there is an edge in one set adjacent to an edge in the other set. The line completion number lc ( G ) of a graph G is the least index r for which L r ( G ) is complete. In this paper we investigate the line completion number of K m , n . This turns out to be an interesting optimization problem in number theory, with results depending on the parities of m and n . If m ≤ n and m is a fixed even number, then lc ( K m , n ) has been found for all even values of n and for all but finitely many odd values. However, when m is odd, the exact value of lc ( K m , n ) has been found in relatively few cases, and the main results concern lower bounds for the parameter. Thus, the general problem is still open, with about half of the cases unsettled.

Authors:Muhammad Irfan; Andrea Semaničová-Feňovčíková Pages: 191 - 199 Abstract: Publication date: Available online 29 June 2016 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Muhammad Irfan, Andrea Semaničová-Feňovčíková Let G = ( V , E ) be a finite, simple and undirected graph. The edge-magic total or vertex-magic total labeling of G is a bijection f from V ( G ) ∪ E ( G ) onto the set of consecutive integers { 1 , 2 , … , V ( G ) + E ( G ) } , such that all the edge weights or vertex weights are equal to a constant, respectively. When all the edge weights or vertex weights are different then the labeling is called edge-antimagic or vertex-antimagic total, respectively. In this paper we provide some classes of graphs that are simultaneously super edge-magic total and super vertex-antimagic total, that is, graphs admitting labeling that has both properties at the same time. We show several results for fans, sun graphs, caterpillars and prisms.

Authors:Gee-Choon Lau; Wai Chee Shiu; Ho-Kuen Ng Pages: 200 - 209 Abstract: Publication date: Available online 29 June 2016 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Gee-Choon Lau, Wai Chee Shiu, Ho-Kuen Ng Let G = ( V ( G ) , E ( G ) ) be a simple, finite and undirected graph of order p and size q . A bijection f : V ( G ) ∪ E ( G ) → { k , k + 1 , k + 2 , … , k + p + q − 1 } such that f ( u v ) = f ( u ) − f ( v ) for every edge u v ∈ E ( G ) is said to be a k -super graceful labeling of G . We say G is k -super graceful if it admits a k -super graceful labeling. For k = 1 , the function f is called a super graceful labeling and a graph is super graceful if it admits a super graceful labeling. In this paper, we study the super gracefulness of complete graph, the disjoint union of certain star graphs, the complete tripartite graphs K ( 1 , 1 , n ) , and certain families of trees. We also present four methods of constructing new super graceful graphs. In particular, all trees of order at most 7 are super graceful. We conjecture that all trees are super graceful.

Authors:S. Arumugam; Joe Ryan; Martin Bača; Kiki Ariyanti Sugeng; S. Slamin; Bharathi Rajan; Dalibor Froncek Pages: 210 - 211 Abstract: Publication date: August 2016 Source:AKCE International Journal of Graphs and Combinatorics, Volume 13, Issue 2 Author(s): S. Arumugam, Joe Ryan, Martin Bača, Kiki Ariyanti Sugeng, S. Slamin, Bharathi Rajan, Dalibor Froncek

Authors:A. Mallika; R. Kala Abstract: Publication date: Available online 10 December 2016 Source:AKCE International Journal of Graphs and Combinatorics Author(s): A. Mallika, R. Kala Let R be a commutative ring and I be a non-zero ideal of R . Let R ⋈ I be the subring of R × R consisting of the elements ( r , r + i ) for r ∈ R and i ∈ I . In this paper we characterize all isomorphism classes of finite commutative rings R with identity and ideal I such that Γ ( R ⋈ I ) is planar. We determine the number of vertices of Γ ( R ⋈ I ) , a necessary and sufficient condition for the graph Γ ( R ⋈ I ) to be outerplanar and the domination number of Γ ( R ⋈ I ) .

Authors:P. Hemalatha; A. Muthusamy Abstract: Publication date: Available online 9 December 2016 Source:AKCE International Journal of Graphs and Combinatorics Author(s): P. Hemalatha, A. Muthusamy For any graph G , let G ∗ be the symmetric digraph obtained from G by replacing every edge with a pair of symmetric arcs. In this paper, we show that the necessary and sufficient condition for the existence of an S ¯ k -factorization in ( C m ∘ K ¯ n ) ∗ is n ≡ 0 ( mod k ( k − 1 ) 2 ) , where k > 3 is odd. In fact, our result deduces the result of Ushio on symmetric complete tripartite digraphs as a corollary. Further, a necessary condition and some sufficient conditions for the existence of an S ¯ k -factorization in K n 1 , n 2 , … , n m ∗ are obtained.

Authors:Shehnaz Akhter; Muhammad Imran Mohammad Reza Farahani Abstract: Publication date: Available online 8 December 2016 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Shehnaz Akhter, Muhammad Imran, Mohammad Reza Farahani In the study of structure-dependency of the total π -electron energy in 1972, it was shown that this energy depends on the degree based sum ∑ v ∈ V d e g G ( v ) 2 and ∑ v ∈ V d e g G ( v ) 3 , where d e g ( v ) is the degree of a vertex of under consideration molecular graph G . Later on, the sum ∑ v ∈ V d e g G ( v ) 2 was named as first Zagreb index. An extensive research work has been done on the Zagreb index and its variants and generalizations, and it become the most investigated topological index in chemical graph theory. But the sum ∑ v ∈ V d e g G ( v ) 3 has been never further investigated, except only it was used in finding some of the general first Zagreb index and the zeroth-order general Randić index. Recently, this sum was renamed Forgotten index or F -index and it was shown to have an exceptional applicative potential. In this paper, we determine the extremal graphs with respect to the F -index among the classes of connected unicyclic and bicyclic graphs.

Authors:T. Tamizh Chelvam; T. Asir Abstract: Publication date: Available online 8 December 2016 Source:AKCE International Journal of Graphs and Combinatorics Author(s): T. Tamizh Chelvam, T. Asir There are so many ways to construct graphs from algebraic structures. Most popular constructions are Cayley graphs, commuting graphs and non-commuting graphs from finite groups and zero-divisor graphs and total graphs from commutative rings. For a commutative ring R with non-zero identity, we denote the set of zero-divisors and unit elements of R by Z ( R ) and U ( R ) , respectively. One of the associated graphs to a ring R is the zero-divisor graph; it is a simple graph with vertex set Z ( R ) ∖ { 0 } , and two vertices x and y are adjacent if and only if x y = 0 . This graph was first introduced by Beck, where all the elements of R are considered as the vertices. Anderson and Badawi, introduced the total graph of R , as the simple graph with all elements of R as vertices, and two distinct vertices x and y are adjacent if and only if x + y ∈ Z ( R ) . For a given graph G , the concept of connectedness, diameter and girth are always of great interest. Several authors extensively studied about the zero-divisor and total graphs from commutative rings. In this paper, we present a survey of results obtained with regard to distances in zero-divisor and total graphs.

Authors:Purnima Gupta; Rajesh Singh; S. Arumugam Abstract: Publication date: Available online 7 December 2016 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Purnima Gupta, Rajesh Singh, S. Arumugam A set D of vertices in a graph G = ( V , E ) is said to be a point-set dominating set (or, in short, psd-set) of G if for every subset S of V − D there exists a vertex v ∈ D such that the subgraph 〈 S ∪ { v } 〉 is connected; the set of all psd-sets of G will be denoted D p s ( G ) . The point-set domination number of a graph denoted by γ p ( G ) is the minimum cardinality of a psd-set of G . We obtain a lower bound for γ p ( G ) and characterize graphs which attain this bound. A psd-set D of a graph G is minimal if no proper subset of D is a psd-set of G . In this paper, we give a general characterization of psd-sets which are minimal. Also, in the case of separable graphs, we obtain more transparent and structure specific characterizations of minimal psd-sets.

Authors:P. Deepa; P. Srinivasan; M. Sundarakannan Abstract: Publication date: Available online 7 December 2016 Source:AKCE International Journal of Graphs and Combinatorics Author(s): P. Deepa, P. Srinivasan, M. Sundarakannan Let G = ( V , E ) be a graph. A local coloring of a graph G of order at least 2 is a function c : V ( G ) ⟶ N having the property that for each set S ⊆ V ( G ) with 2 ≤ S ≤ 3 , there exist vertices u , v ∈ S such that c ( u ) − c ( v ) ≥ m s , where m s is the size of the induced subgraph 〈 S 〉 . The maximum color assigned by a local coloring c to a vertex of G is called the value of c and is denoted by χ ℓ ( c ) . The local chromatic number of G is χ ℓ ( G ) = min { χ ℓ ( c ) } , where the minimum is taken over all local colorings c of G . In this paper we study the local coloring for some self complementary graphs. Also we present a sc-graph with local chromatic number k for any given integer k ≥ 6 .

Authors:Andrea Martin; Marcela Abstract: Publication date: Available online 3 December 2016 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Andrea Semaničová-Feňovčíková, Martin Bača, Marcela Lascsáková Let H be a graph. A graph G = ( V , E ) admits an H -covering if every edge in E belongs to a subgraph of G isomorphic to H . A graph G admitting an H -covering is called ( a , d ) - H -antimagic if there is a bijection f : V ( G ) ∪ E ( G ) → { 1 , 2 , … , V ( G ) + E ( G ) } such that for each subgraph H ′ of G isomorphic to H , the sum of labels of all the edges and vertices belonged to H ′ constitute the arithmetic progression with the initial term a and the common difference d . Such a graph is called super if f ( V ( G ) ) = { 1 , 2 , 3 , … , V ( G ) } . In this paper, we provide two constructions of (super) H -antimagic graphs obtained from smaller (super) H ′ -antimagic graphs.

Authors:Roy Abstract: Publication date: Available online 3 December 2016 Source:AKCE International Journal of Graphs and Combinatorics Author(s): S. Roy The packing chromatic number χ ρ ( G ) of a graph G is the smallest integer k for which there exists a mapping π : V ( G ) ⟶ { 1 , 2 , … , k } such that any two vertices of color i are at distance at least i + 1 . In this paper, we compute the packing chromatic number for certain fan and wheel related graphs.

Authors:Terry A. McKee Abstract: Publication date: Available online 2 December 2016 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Terry A. McKee A set of vertices whose deletion from a graph would increase the distance between two remaining vertices is called a weak vertex separator of the graph. Two vertices form a two-pair if all chordless paths between them have length 2 . I prove that every inclusion-minimal weak vertex separator of every induced subgraph of a graph G induces a complete subgraph if and only if nonadjacent vertices of induced C 4 subgraphs of G always form two-pairs of G ; moreover, this is also true when “complete” and C 4 are replaced with “edgeless” and K 4 − e ( ≅ K 1 , 1 , 2 ). The first of the resulting new graph classes generalizes chordal graphs, and the second generalizes unichord-free graphs; they both generalize distance-hereditary graphs and geodetic graphs.

Authors:Michael Haythorpe Abstract: Publication date: Available online 27 October 2016 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Michael Haythorpe The generalised Sudoku problem with N symbols is known to be NP-complete, and hence is equivalent to any other NP-complete problem, even for the standard restricted version where N is a perfect square. In particular, generalised Sudoku is equivalent to the, classical, Hamiltonian cycle problem. A constructive algorithm is given that reduces generalised Sudoku to the Hamiltonian cycle problem, where the resultant instance of Hamiltonian cycle problem is sparse, and has O ( N 3 ) vertices. The Hamiltonian cycle problem instance so constructed is a directed graph, and so a (known) conversion to undirected Hamiltonian cycle problem is also provided so that it can be submitted to the best heuristics. A simple algorithm for obtaining the valid Sudoku solution from the Hamiltonian cycle is provided. Techniques to reduce the size of the resultant graph are also discussed.

Authors:Abolape D. Akwu; Deborah Olayide A. Ajayi Abstract: Publication date: Available online 10 September 2016 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Abolape D. Akwu, Deborah Olayide A. Ajayi For any integer r ≥ 3 , we define the sunlet graph of order 2 r , denoted L 2 r , as the graph consisting of a cycle of length r together with r pendant vertices, each adjacent to exactly one vertex of the cycle. In this paper, we give necessary and sufficient conditions for decomposing the lexicographic product of the complete graph and the complete graph minus a 1-factor, with complement of the complete graph K m , (that is K n ⊗ K ̄ m and K n − I ⊗ K ̄ m , respectively) into sunlet graphs of order twice a prime.

Authors:K. Selvakumar; M. Subajini Abstract: Publication date: Available online 31 August 2016 Source:AKCE International Journal of Graphs and Combinatorics Author(s): K. Selvakumar, M. Subajini The non-cyclic graph C G to a non locally cyclic group G is as follows: take G ∖ C y c ( G ) as vertex set, where C y c ( G ) = { x ∈ G 〈 x , y 〉 is cyclic for all y ∈ G } is called the cyclicizer of G , and join two vertices if they do not generate a cyclic subgroup. In this paper, we classify the finite groups whose non-cyclic graphs are outerplanar. Also all finite groups whose non-cyclic graphs can be embedded on the torus or projective plane are classified.

Authors:Jia-Bao Liu; Wei Gao Muhammad Kamran Siddiqui Muhammad Reza Farahani Abstract: Publication date: Available online 6 August 2016 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Jia-Bao Liu, Wei Gao, Muhammad Kamran Siddiqui, Muhammad Reza Farahani A numeric quantity which characterizes the whole structure of a graph is called a topological index. The concept of Generalized Zagreb, atom–bond connectivity ( A B C ) and geometric–arithmetic ( G A ) topological indices was established in chemical graph theory based on vertex degrees. Later on, other versions of A B C and G A indices were introduced and some of the versions of these indices are recently designed. In this article, we compute, Generalized Zagreb index G Z , fourth version of atom–bond connectivity ( A B C 4 ) index and fifth version of geometric–arithmetic ( G A 5 ) index for an infinite class of Titania nanotubes TiO 2 [ m , n ] .

Authors:S.M. Hegde; Suresh Dara Abstract: Publication date: Available online 3 August 2016 Source:AKCE International Journal of Graphs and Combinatorics Author(s): S.M. Hegde, Suresh Dara Let G be a graph and K G be the set of all cliques of G , then the clique graph of G denoted by K ( G ) is the graph with vertex set K G and two elements Q i , Q j ∈ K G form an edge if and only if Q i ∩ Q j ≠ 0̸ . Iterated clique graphs are defined by K 0 ( G ) = G , and K n ( G ) = K ( K n − 1 ( G ) ) for n > 0 . In this paper we prove a necessary and sufficient condition for a clique graph K ( G ) to be complete when G = G 1 + G 2 , give a partial characterization for clique divergence of the join of graphs and prove that if G 1 , G 2 are Clique-Helly graphs different from K 1 and G = G 1 □ G 2 , then K 2 ( G ) = G .

Authors:L. Jones Tarcius Doss; P. Arathi Abstract: Publication date: Available online 25 July 2016 Source:AKCE International Journal of Graphs and Combinatorics Author(s): L. Jones Tarcius Doss, P. Arathi In this paper, a new viable bandwidth reduction algorithm for reducing the bandwidth of sparse symmetric matrices, is described. The proposed algorithm provides a reliable procedure to reduce the bandwidth and can easily be applied to the sparse symmetric matrices of any size. This algorithm is tested on structured graphs and the reduced bandwidth results obtained are compared with the GPS algorithm. The bandwidth obtained by the present method is smaller than or equal to the one obtained by the GPS and standard examples are included to illustrate in detail the proposed algorithm.

Authors:Ratinan Boonklurb; Authawich Narissayaporn Sirirat Singhun Abstract: Publication date: Available online 22 July 2016 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Ratinan Boonklurb, Authawich Narissayaporn, Sirirat Singhun We generalize the notion of the super edge-magic labeling of graphs to the notion of the super edge-magic labeling of hypergraphs. For a hypergraph H with a finite vertex set V and a hyperedge set E , a bijective function f : V ∪ E → { 1 , 2 , 3 , … , V + E } is called a super edge-magic labeling if it satisfies (i) there exists a magic constant Λ such that f ( e ) + ∑ v ∈ e f ( v ) = Λ for all e ∈ E and (ii) f ( V ) = { 1 , 2 , 3 , … , V } . A hypergraph admitting a super edge-magic labeling is said to be super edge-magic. In this paper, we show the equivalent form of this labeling, i.e, a hypergraph H is super edge-magic if and only if there exists a bijective function f : V → { 1 , 2 , 3 , … , V } such that { ∑ v ∈ e f ( v ) e ∈ E } is the set of E consecutive integers. Finally, we define two classes of hypergraphs, namely m -node k -uniform hyperpaths and m -node k -uniform hypercycles which are denoted by m P n ( k ) and m C n ( k ) , respectively. We show that under some conditions the hypergraphs m P n ( k ) and m C n ( k ) are super edge-magic.

Authors:I. Tarawneh; R. Hasni; A. Ahmad Abstract: Publication date: Available online 19 July 2016 Source:AKCE International Journal of Graphs and Combinatorics Author(s): I. Tarawneh, R. Hasni, A. Ahmad In this paper, we investigate the new graph characteristic, the edge irregularity strength, denoted as es, as a modification of the well known irregularity strength, total edge irregularity strength and total vertex irregularity strength. As a result, we obtain the exact value of an edge irregularity strength of corona product of cycle with isolated vertices.

Authors:G. Indulal; R. Balakrishnan Abstract: Publication date: Available online 13 July 2016 Source:AKCE International Journal of Graphs and Combinatorics Author(s): G. Indulal, R. Balakrishnan The D -eigenvalues μ 1 , μ 2 , … , μ n of a graph G of order n are the eigenvalues of its distance matrix D and form the distance spectrum or D -spectrum of G denoted by S p e c D ( G ) . Let G 1 and G 2 be two regular graphs. The Indu–Bala product of G 1 and G 2 is denoted by G 1 ▾ G 2 and is obtained from two disjoint copies of the join G 1 ∨ G 2 of G 1 and G 2 by joining the corresponding vertices in the two copies of G 2 . In this paper we obtain the distance spectrum of G 1 ▾ G 2 in terms of the adjacency spectra of G 1 and G 2 . We use this result to obtain a new class of distance equienergetic graphs of diameter 3 . We also prove that the class of graphs K n ¯ ▾ K n + 1 ¯ has integral distance spectrum.

Authors:Hortensia Abstract: Publication date: Available online 25 June 2016 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Hortensia Galeana-Sánchez, Rocío Sánchez-López Let H be a digraph possibly with loops and D a finite digraph without loops whose arcs are colored with the vertices of H ( D is an H -colored digraph). V( D ) and A( D ) will denote the sets of vertices and arcs of D respectively. For an arc ( z 1 , z 2 ) of D we will denote by c D ( z 1 , z 2 ) its color. A directed walk (respectively directed path) ( v 1 , v 2 , … , v n ) in D is an H -walk (respectively H -path) if and only if ( c D ( v 1 , v 2 ), c D ( v 2 , v 3 ) , … , c D ( v n − 1 , v n ) ) is a directed walk in H . A set K ⊆ V ( D ) is an H -kernel by walks (respectively H -kernel) if for every pair of different vertices in K there is no H -walk (respectively H -path) between them, and for every vertex u ∈ V ( D ) ∖ K there exists v ∈ K such that there exists an H -walk (respectively H -path) from u to v in D . Let D be an arc-colored digraph. The color-class digraph of D , denoted by C C ( D ), is defined as follows: the vertices of the color-cl... PubDate: 2016-06-28T23:15:56Z