Authors:Y.M. Borse; Ganesh Mundhe Abstract: Publication date: Available online 26 December 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Y.M. Borse, Ganesh Mundhe In general, the splitting operation on a binary matroid M does not preserve the connectivity of M . In this paper, we provide sufficient conditions to preserve n -connectedness of a binary matroid under splitting operation. As a consequence, for an ( n + 1 ) -connected binary matroid M , we give a precise characterization of when the splitting matroid M T is n -connected.

Authors:Sylwia Cichacz; Irmina A. Zioło Abstract: Publication date: Available online 23 December 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Sylwia Cichacz, Irmina A. Zioło Let G = ( V , E ) be a graph, by V 2 , we mean the set of all 2-combinations of V . We say that a graph G is k -swappable if for every edge e ∈ E , there are two sets A ⊂ E , B ⊂ V 2 ∖ E such that e ∈ A , A ≤ k , and G ≅ ( V , ( E ∖ A ) ∪ B ) . The swapping number of G is the minimum k > 0 such that G is k -swappable. Let d ≥ 2 be an integer. Every tree with exactly one vertex of degree d and remaining vertices of degree d + 1 or 1 we will call a d -nary tree. In this paper we give sufficient conditions for general graphs as well as sufficient and necessary conditions for a d -nary tree for d > 2 to be 2-swappable.

Authors:T. Tamizh Chelvam; M. Sivagami Abstract: Publication date: Available online 21 December 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): T. Tamizh Chelvam, M. Sivagami Let Ω be a symmetric generating set of a finite group Γ . Assume that ( Γ , Ω ) be such that Γ = 〈 Ω 〉 and Ω satisfies the two conditions C 1 : the identity element e ⁄ ∈ Ω and C 2 : if a ∈ Ω , then a − 1 ∈ Ω . Given ( Γ , Ω ) satisfying C 1 and C 2 , define a Cayley graph G = C a y ( Γ , Ω ) with V ( G ) = Γ and E ( G ) = { ( x , y ) a x , y ∈ Γ , a ∈ Ω and y = x a } . When Γ = Z n = 〈 Ω 〉 , it is called as circulant graph and denoted by C i r ( n , Ω ) . In this paper, we give a survey about the results on dominating sets in Cayley graphs and circulant graphs.

Authors:Abdullah Atmaca; A. Yavuz Oruç Abstract: Publication date: Available online 21 December 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Abdullah Atmaca, A. Yavuz Oruç Let B u ( n , r ) denote the set of unlabeled bipartite graphs whose edges connect a set of n vertices with a set of r vertices. In this paper, we provide exact formulas for B u ( 2 , r ) and B u ( 3 , r ) using Polya’s Counting Theorem. Extending these results to n ≥ 4 involves solving a set of complex recurrences and remains open. In particular, the number of recurrences that must be solved to compute B u ( n , r ) is given by the number of partitions of n that is known to increase exponentially with n by Ramanujan–Hardy–Rademacher’s asymptotic formula.

Authors:A. Mallika; R. Kala Abstract: Publication date: Available online 20 December 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): A. Mallika, R. Kala Let R be a commutative ring with identity. The nilpotent graph of R , denoted by Γ N ( R ) , is a graph with vertex set Z N ( R ) ∗ , and two vertices x and y are adjacent if and only if x y is nilpotent, where Z N ( R ) = { x ∈ R : x y is nilpotent, for some y ∈ R ∗ } . In this paper, we characterize finite rings (up to isomorphism) with identity whose nilpotent graphs can be embedded in the projective plane or Klein bottle. Also, we classify finite rings whose nilpotent graphs are ring graph or outerplanarity index 1,2.

Authors:Sasmita Barik; Gopinath Sahoo Abstract: Publication date: Available online 20 December 2017 Source:AKCE International Journal of Graphs and Combinatorics 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 2008, 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.

Authors:Simon Davis Abstract: Publication date: Available online 19 December 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Simon Davis The location of the nontrivial poles of a generalized zeta function is derived from the spectrum of Ramanujan graphs and bounds are established for irregular graphs. The existence of a similarity transformation of the diagonal matrix given by a specified set of eigenvalues to an adjacency matrix of a graph is proven, and the method yields a set of finite graphs with eigenvalues determined approximately by a finite subset of the poles of the Ihara zeta function.

Authors:Niranjan P.K.; Srinivasa Rao Kola Abstract: Publication date: Available online 18 December 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Niranjan P.K., Srinivasa Rao Kola For any positive integer k , a k -distance coloring of a graph G is a vertex coloring of G in which no two vertices at distance less than or equal to k receive the same color. The k -distance chromatic number of G , denoted by χ k G is the smallest integer α for which G has a k -distance α -coloring. In this paper, we improve the lower bound for the k -distance chromatic number of an arbitrary graph for k odd case and see that trees achieve this lower bound by determining the k -distance chromatic number of trees. Also, we find k -distance chromatic number of cycles and 2-distance chromatic number of a graph G in which every pair of cycles are edge disjoint.

Authors:Paul A. Burchett; R. Douglas Chatham Abstract: Publication date: Available online 15 December 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Paul A. Burchett, R. Douglas Chatham For a chessboard graph and a given graph parameter π , a π separation number is the minimum number of pawns for which some arrangement of those pawns on the board will produce a board where π has some desired value. We extend previous results on independence and domination separation. We also consider separation of other domination-related parameters.

Authors:Wenhui Ma; Guanghua Dong; Yingyu Lu; Ning Wang Abstract: Publication date: Available online 14 December 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Wenhui Ma, Guanghua Dong, Yingyu Lu, Ning Wang A graph with q edges is called a n t i m a g i c if its edges can be labeled with 1, 2, … , q such that the sums of the labels on the edges incident to each vertex are distinct. Hartsfield and Ringel conjectured that every connected graph other than K 2 is antimagic. In this paper, through a labeling method and a modification on this labeling, we obtained that the lexicographic product graphs P m [ P n ] are antimagic.

Authors:Mustapha Chellali; Teresa W. Haynes; Stephen T. Hedetniemi Abstract: Publication date: Available online 14 December 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Mustapha Chellali, Teresa W. Haynes, Stephen T. Hedetniemi For any integer k ≥ 0 , a set of vertices S of a graph G = ( V , E ) is k -cost-effective if for every v ∈ S , N ( v ) ∩ ( V ∖ S ) ≥ N ( v ) ∩ S + k . In this paper we study the minimum cardinality of a maximal k -cost-effective set and the maximum cardinality of a k -cost-effective set. We obtain Gallai-type results involving the k -cost-effective and global k -offensive alliance parameters, and we provide bounds on the maximum k -cost-effective number. Finally, we consider k -cost-effective sets that are also dominating. We show that computing the k -cost-effective domination number is NP-complete for bipartite graphs. Moreover, we note that not all trees have a k -cost-effective dominating set and give a constructive characterization of those that do.

Authors:Dijian Wang; Yaoping Hou; Zikai Tang Abstract: Publication date: Available online 20 November 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Dijian Wang, Yaoping Hou, Zikai Tang Let G be a graph and A = A ( G ) be its adjacency matrix. The eigenvalues μ 1 , μ 2 , … , μ n of A ( G ) are the eigenvalues of G and form the adjacency spectrum, denoted by S p e c ( G ) . In this paper, we introduce two new operations G 1 ■ k ( G 3 □ G 2 ) and ( G 4 □ G 1 ) ■ k ( G 3 □ G 2 ) , and describe the adjacency spectra of G 1 ■ k ( G 3 □ G 2 ) and ( G 4 □ G 1 ) ■ k ( G 3 □ G 2 ) of regular graphs G 1 , G 2 and arbitrarily graphs G 3 , G 4 in terms of their adjacency spectra. As the applications, we obtain some new integral spectrum graphs.

Authors:Arpita Das; Pratima Panigrahi Abstract: Publication date: Available online 8 November 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Arpita Das, Pratima Panigrahi In this paper we determine the full normalized Laplacian spectrum of the subdivision-vertex join, subdivision-edge join, R -vertex join, and R -edge join of two regular graphs in terms of the normalized Laplacian eigenvalues of the graphs. Moreover, applying these results we find non-regular normalized Laplacian cospectral graphs.

Authors:Koko K. Kayibi; S. Pirzada; T.A. Chishti Abstract: Publication date: Available online 1 November 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Koko K. Kayibi, S. Pirzada, T.A. Chishti Let Ω be the set of all m × n matrices, where r i and c j are the sums of entries in row i and column j , respectively. Sampling efficiently uniformly at random elements of Ω is a problem with interesting applications in Combinatorics and Statistics. To calibrate the statistic χ 2 for testing independence, Diaconis and Gangolli proposed a Markov chain on Ω that samples uniformly at random contingency tables of fixed row and column sums. Although the scheme works well for practical purposes, no formal proof is available on its rate of convergence. By using a canonical path argument, we prove that this Markov chain is fast mixing and the mixing time τ x ( ϵ ) is given by τ x ( ϵ ) ≤ 2 c m a x ( m n ) 4 ln ( c m a x ϵ − 1 ) , where c m a x − 1 is the maximal value in a cell.

Authors:Nurdin Hinding; Dian Firmayasari; Hasmawati Basir; Martin Bača; Andrea Semaničová-Feňovčíková Abstract: Publication date: Available online 28 October 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Nurdin Hinding, Dian Firmayasari, Hasmawati Basir, Martin Bača, Andrea Semaničová-Feňovčíková In this paper we investigate the total edge irregularity strength tes ( G ) and the total vertex irregularity strength tvs ( G ) of diamond graphs B r n and prove that tes ( B r n ) = ( 5 n − 3 ) ∕ 3 , while tvs ( B r n ) = ( n + 1 ) ∕ 3 .

Authors:T. Tamizh Chelvam; T. Asir Abstract: Publication date: Available online 23 October 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): T. Tamizh Chelvam, T. Asir Let R be a commutative ring. The total graph T Γ ( R ) of R is the undirected graph with vertex set R and two distinct vertices x and y are adjacent if x + y is a zero divisor in R . In this paper, we present a survey of results on the genus of T Γ ( R ) and three of its generalizations.

Authors:Ivan Gutman; Boris Furtula; Vladimir Katanić Abstract: Publication date: Available online 14 October 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Ivan Gutman, Boris Furtula, Vladimir Katanić The Randić index R G is one of the classical graph-based molecular structure descriptors that found countless applications in chemistry and pharmacology. The mathematical background of this index is also well elaborated. We now point out a hitherto unnoticed feature of R G , namely its connection with the degree-based information content of a (molecular) graph. This connection is based on the linear correlation between R G and the logarithm of the multiplicative version of the Randić index.

Authors:Yoshimi Egawa; Keiko Kotani; Shunsuke Nakamura Abstract: Publication date: Available online 13 October 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Yoshimi Egawa, Keiko Kotani, Shunsuke Nakamura Let G be a 4-connected graph, and let E ̃ ( G ) denote the set of those edges of G which are not contained in a triangle, and let E c ( G ) denote the set of 4-contractible edges of G . We show that if 3 ≤ E ̃ ( G ) ≤ 4 or E ̃ ( G ) ≥ 7 , then E c ( G ) ≥ ( E ̃ ( G ) + 8 ) ∕ 4 unless G has one of the three specified configurations.

Authors:Chernyi Sergei Abstract: Publication date: Available online 6 October 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Chernyi Sergei Currently, there is an increased interest in the tools and methods of active control of generation and consumption of the inactive energy flows. Particularly, the task is relevant for autonomous electric power systems operating on a non-linear load. At the same time, the inactive energy flows is required to be controlled according to the specified law in order to impart the desired properties to autonomous systems. In general, with a high degree of automation on board the ships of the world fleet, the task of improving the efficiency of the automatic control of electricity quality remains urgent to them. This issue has arisen due to the fact that the semiconductor converters of electricity are becoming more widely used in the ship’s autonomous power systems. A scheme has been developed on the Ethernet platform for optimizing system performance of maritime platforms. The research was focused on the offshore platforms that operate in the Black Sea.

Authors:Jung Kyu Park; Jaeho Kim Abstract: Publication date: Available online 6 October 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Jung Kyu Park, Jaeho Kim Recently, a large amount of multimedia data is rapidly increasing due to cloud activation. For this reason, there is a need for a technique capable of handling large amounts of data and large storage devices. In this way, a network storage device such as a NAS or a SAN is used to configure a large-capacity storage device in a network environment. In this paper, a large capacity storage device is constructed by using network direct connection storage device. We performed benchmark experiments to verify the scalability of the constructed storage devices using network direct attached storage.

Authors:Kaemawichanurat Jiarasuksakun Abstract: Publication date: Available online 4 October 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): P. Kaemawichanurat, T. Jiarasuksakun A k - γ c -critical graph is a graph G with connected domination number γ c ( G ) = k and γ c ( G + u v ) < k for any pair of non-adjacent vertices u and v of G . Let ω and α be respectively the clique number and the independence number of a graph. In this paper, we prove that every k - γ c -critical graph satisfies α + ω ≤ n − ⌊ k 2 ⌋ + 1 for 1 ≤ k ≤ 3 . We also characterize all 3 - γ c -critical graphs achieving the upper bound. For k ≥ 4 , we show that there are infinitely many k - γ c -critical graphs satisfying α + ω = n − ⌊ k 2 ⌋ + 1 . Thus, we conclude this paper with an open problem that every k - γ c -critical graph for k ≥ 4 satisfies α + ω ≤ n − ⌊ k 2 ⌋ + 1 .

Authors:Kristiana Wijaya; Edy Tri Baskoro; Hilda Assiyatun; Djoko Suprijanto Abstract: Publication date: Available online 28 September 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Kristiana Wijaya, Edy Tri Baskoro, Hilda Assiyatun, Djoko Suprijanto Let F , G , and H be simple graphs. We write F → ( G , H ) to mean that any red–blue coloring of all edges of F will contain either a red copy of G or a blue copy of H . A graph F (without isolated vertices) satisfying F → ( G , H ) and for each e ∈ E ( F ) , ( F − e ) ↛ ( G , H ) is called a Ramsey ( G , H ) -minimal graph. The set of all Ramsey ( G , H ) -minimal graphs is denoted by ℛ ( G , H ) . In this paper, we derive the necessary and sufficient condition of graphs belonging to ℛ ( 4 K 2 , H ) , for any connected graph H . Moreover, we give a relation between Ramsey ( 4 K 2 , P 3 ) - and ( 3 K 2 , P 3 ) -minimal graphs, and Ramsey ( 4 K 2 , P 3 ) - and ( 2 K 2 , P 3 ) -minimal graphs. Furthermore, we determine all graphs in ℛ ( 4 K 2 , P 3 ) .

Authors:Siddharth Bhatia; Kunal Lad; Rajiv Kumar Abstract: Publication date: Available online 12 September 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Siddharth Bhatia, Kunal Lad, Rajiv Kumar A drawing of a plane graph G in which each edge is represented by a sequence of alternating horizontal and vertical line segments is called an orthogonal drawing. The points of intersection of horizontal and vertical line segments of an edge in an orthogonal drawing are called bends. The best known algorithm to find a bend-optimal orthogonal drawing of a plane graph takes time O ( n 1 . 5 ) where n is the number of vertices in the graph. In this paper we present a new linear time algorithm to find an orthogonal drawing of a plane 3-connected graph (with maximum degree 4) and give bounds on number of bends (in terms of number k of degree-4 vertices in the graph) in the resulting drawing with respect to the number b ( G ) of bends in the bend-optimal orthogonal drawing of the same graph. The bound is b ( G ) + 3 k .

Authors:Mohammed M.M. Jaradat; Mohammad S. Bataineh; Tomáš Vetrík; Ayat M.M. Rabaiah Abstract: Publication date: Available online 11 September 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Mohammed M.M. Jaradat, Mohammad S. Bataineh, Tomáš Vetrík, Ayat M.M. Rabaiah The study of exact values and bounds on the Ramsey numbers of graphs forms an important family of problems in the extremal graph theory. For a set of graphs S and a graph F , the Ramsey number R ( S , F ) is the smallest positive integer r such that for every graph G on r vertices, G contains a graph in S as a subgraph or the complement of G contains F as a subgraph. Ramsey numbers of various graphs including theta graphs and wheels have been extensively studied. We extend known results in the area by presenting exact values of the Ramsey numbers R ( θ n , W 5 ) for n ≥ 7 , where θ n is the set of theta graphs of order n and W 5 is the wheel graph of order 5 .

Authors:K. Pattabiraman Abstract: Publication date: Available online 15 August 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): K. Pattabiraman The inverse sum indeg index I S I ( G ) of a simple graph G is defined as the sum of the terms d G ( u ) d G ( v ) d G ( u ) + d G ( v ) over all edges u v of G , where d G ( u ) denotes the degree of a vertex u of G . In this paper, we present several upper and lower bounds on the inverse sum indeg index in terms of some molecular structural parameters and relate this index to various well-known molecular descriptors.

Authors:Qiong Wu; Wai Chee Shiu Abstract: Publication date: Available online 14 August 2017 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Qiong Wu, Wai Chee Shiu For j ≤ k , the L ( j , k ) -labeling arose from code assignment problem. That is, let j , k and m be positive numbers, an m - L ( j , k ) -labeling of a graph G is a mapping f : V ( G ) → [ 0 , m ] such that f ( u ) − f ( v ) ≥ j if d ( u , v ) = 1 , and f ( u ) − f ( v ) ≥ k if d ( u , v ) = 2 . The span of f is the difference between the maximum and the minimum numbers assigned by f . The L ( j , k ) -labeling number of G , denoted by λ j , k ( G ) , is the minimum span over all L ( j , k ) -labelings of G . The k th power G k of an undirected graph G is the graph with the vertex set of G in which two vertices are adjacent when their distance in G is at most k . In this paper, the L ( j , k ) -labeling numbers of P n 2 are determined for j ≤ k .

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: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: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: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.