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:Kahina Ouazine; Hachem Slimani; Abdelkamel Tari Abstract: Publication date: Available online 9 June 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Kahina Ouazine, Hachem Slimani, Abdelkamel Tari In practice, an alliance can be a bond or connection between individuals, families, states, or entities, etc. Formally, a non-empty set S of vertices of a graph G is a defensive k -alliance (resp. an offensive k -alliance) if every vertex of S (resp. the boundary of S ) has at least k more neighbors inside of S than it has outside of S . A powerful k -alliance is both defensive k -alliance and offensive ( k + 2 ) -alliance. During the last decade there has been a remarkable development on these three kinds of alliances. Due to their variety of applications, the alliances in its broad sense have received a special attention from many scientists and researchers. There have been applications of alliances in several areas such as bioinformatics, distributed computing, web communities, social networks, data clustering, business, etc. Several k -alliance numbers have been defined and a huge number of theoretical (algorithmic and computational) results are obtained for various graph classes. In this paper, we present a survey which covers a number of practical applications of alliances and the vast mathematical properties of the three types of k -alliances by giving a special attention to the study of the associated k -alliance (partition) numbers for different graph classes.

Authors:Roger Vargas; Abigail Waldron Anika Sharma Rigoberto Darren Narayan Abstract: Publication date: Available online 7 June 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Roger Vargas, Abigail Waldron, Anika Sharma, Rigoberto Flórez, Darren A. Narayan In 2010, Joyce et al. defined the leverage centrality of vertices in a graph as a means to analyze functional connections within the human brain. In this metric a degree of a vertex is compared to the degrees of all it neighbors. We investigate this property from a mathematical perspective. We first outline some of the basic properties and then compute leverage centralities of vertices in different families of graphs. In particular, we show there is a surprising connection between the number of distinct leverage centralities in the Cartesian product of paths and the triangle numbers.

Authors:A.K. Handa; Aloysius Godinho; T. Singh; S. Arumugam Abstract: Publication date: Available online 19 May 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): A.K. Handa, Aloysius Godinho, T. Singh, S. Arumugam 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 v with respect to f is defined by w f ( v ) = ∑ x ∈ N ( v ) f ( x ) , where N ( v ) is the open neighborhood of v . The labeling f is said to be distance antimagic if w f ( u ) ≠ w f ( v ) for every pair of distinct 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 labelings of G + H and G ∘ H .

Authors:Deepti Jain; Purnima Gupta; S. Arumugam Abstract: Publication date: Available online 18 May 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Deepti Jain, Purnima Gupta, S. Arumugam A set D ⊆ V ( G ) is a 2-point set dominating set (2-psd set) of a graph G if for any subset S ⊆ V − D , there exists a non-empty subset T ⊆ D containing at most two vertices such that the induced subgraph 〈 S ∪ T 〉 is connected. In this paper we characterize minimal 2-psd sets for a general graph. Based on the structure we examine 2-psd sets in a separable graph and discuss the criterion for a 2-psd set to be minimal.

Authors:Masao Tsugaki; Guiying Yan Abstract: Publication date: Available online 17 May 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Masao Tsugaki, Guiying Yan Let k ≥ 2 , l ≥ 1 and m ≥ 0 be integers, and let G be an l -connected graph. If there exists a subgraph X of G such that the distance between v and X is at most m for any v ∈ V ( G ) , then we say that X m -dominates G . A subset S of V ( G ) is said to be 2 ( m + 1 ) -stable if the distance between each pair of distinct vertices in S is at least 2 ( m + 1 ) . In this paper, we prove that if G does not have a 2 ( m + 1 ) -stable set of order at least k + l , then G has an m -dominating tree which has at most k leaves.

Authors:K. Teerapabolarn Abstract: Publication date: Available online 11 May 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): K. Teerapabolarn In this article, we use Stein’s method together with z -functions to give an improved bound for the total variation distance between the distribution of a non-negative integer-valued random variable X and the negative binomial distribution with parameters r ∈ R + and p = 1 − q ∈ ( 0 , 1 ) , where r q p is equal to the mean of X , E ( X ) . The improved bound is sharper than that mentioned in Teerapabolarn and Boondirek (2010). We give three examples of the negative binomial approximation to the distribution of X concerning the negative hypergeometric, Pólya and negative Pólya distributions.

Authors:R. El-Shanawany; A. El-Mesady Abstract: Publication date: Available online 2 May 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): R. El-Shanawany, A. El-Mesady In this article, a technique to construct cyclic orthogonal double covers (CODCs) of regular circulant graphs by certain infinite graph classes such as complete bipartite and tripartite graphs and disjoint union of butterfly and K 1 , 2 n − 10 is introduced.

Authors:Novi H. Bong Abstract: Publication date: Available online 2 May 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Novi H. Bong The extremal number e x ( n ; { C 3 , C 4 } ) or simply e x ( n ; 4 ) denotes the maximal number of edges in a graph on n vertices with forbidden subgraphs C 3 and C 4 . The exact number of e x ( n ; 4 ) is only known for n up to 32 and n = 50 . There are upper and lower bounds of e x ( n ; 4 ) for other values of n . In this paper, we improve the upper bound of e x ( n ; 4 ) for n = 33 , 34 , … , 42 and also n = d 2 + 1 for any positive integer d ≠ 7 , 57 .

Authors:Kukil Kalpa Rajkhowa; Helen K. Saikia Abstract: Publication date: Available online 28 April 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Kukil Kalpa Rajkhowa, Helen K. Saikia For a non-commutative ring R , the left total directed graph of R is a directed graph with vertex set as R and for the vertices x and y , x is adjacent to y if and only if there is a non-zero r ∈ R which is different from x and y , such that r x + y r is a left zero-divisor of R . In this paper, we discuss some very basic results of left (as well as right) total directed graph of R . We also study the coloring of left total directed graph of R directed graph.

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.