Authors:S.A. Tapadia; B.N. Waphare Abstract: Publication date: Available online 21 February 2018 Source:AKCE International Journal of Graphs and Combinatorics Author(s): S.A. Tapadia, B.N. Waphare In 1992, Bagga, Beineke, and Varma introduced the concept of the super line graph of index r of a graph G , denoted by ℒ r ( G ) . The vertices of ℒ r ( G ) are the r -subsets of E ( G ) , and two vertices S and T are adjacent if there exist s ∈ S and t ∈ T such that s and t are adjacent edges in G . They also defined the line completion number l c ( G ) of graph G to be the minimum index r for which ℒ r ( G ) is complete. They found the line completion number for certain classes of graphs. In this paper, we find the line completion number of hypercube Q n for every n .

Authors:Saeid Alikhani; Samaneh Soltani Abstract: Publication date: Available online 21 February 2018 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Saeid Alikhani, Samaneh Soltani The distinguishing number D ( G ) of a graph G is the least integer d such that G has a vertex labeling with d labels that is preserved only by a trivial automorphism. In this paper we characterize all trees with radius at most three and distinguishing number two. Also we present a necessary condition for trees with distinguishing number two and radius more than three.

Authors:Mohamed Bouzefrane; Saliha Ouatiki Abstract: Publication date: Available online 15 February 2018 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Mohamed Bouzefrane, Saliha Ouatiki For a graph G = ( V , E ) , a set S ⊆ V is a dominating set if every vertex in V − S has at least a neighbor in S . A dominating set S is a global offensive alliance if for each vertex v in V − S at least half the vertices from the closed neighborhood of v are in S . The domination number γ ( G ) is the minimum cardinality of a dominating set of G , and the global offensive alliance number γ o ( G ) is the minimum cardinality of a global offensive alliance of G . We show that if G is a connected unicycle graph of order n with l ( G ) leaves and s ( G ) support vertices then γ o ( G ) ≥ n − l ( G ) + s ( G ) 3 . Moreover, we characterize all extremal unicycle graphs attaining this bound.

Authors:Ika Hesti Agustin; R.M. Prihandini; Dafik Abstract: Publication date: Available online 13 February 2018 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Ika Hesti Agustin, R.M. Prihandini, Dafik Let L and H be two simple, nontrivial and undirected graphs. Let o be a vertex of H , the comb product between L and H , denoted by L ▹ H , is a graph obtained by taking one copy of L and V ( L ) copies of H and grafting the i th copy of H at the vertex o to the i th vertex of L . By definition of comb product of two graphs, we can say that V ( L ▹ H ) = { ( a , v ) a ∈ V ( L ) , v ∈ V ( H ) } and ( a , v ) ( b , w ) ∈ E ( L ▹ H ) whenever a = b and v w ∈ E ( H ) , or a b ∈ E ( L ) and v = w = o . Let G = L ▹ H and P 2 ▹ H ⊆ G , the graph G is said to be an ( a , d ) - P 2 ▹ H -antimagic total graph if there exists a bijective function f : V ( G ) ∪ E ( G ) → { 1 , 2 , … , V ( G ) + E ( G ) } such that for all subgraphs isomorphic to P 2 ▹ H , the total P 2 ▹ H -weights W ( P 2 ▹ H ) = ∑ v ∈ V ( P 2 ▹ H ) f ( v ) + ∑ PubDate: 2018-02-26T18:40:01Z DOI: 10.1016/j.akcej.2018.01.008

Authors:N.B. Mumba; E. Mwambene Abstract: Publication date: Available online 13 February 2018 Source:AKCE International Journal of Graphs and Combinatorics Author(s): N.B. Mumba, E. Mwambene Hofmeister considered the automorphism groups of antipodal graphs through the exploration of graph covers. In this note we extend the exploration of automorphism groups of distance preserving graph covers. We apply the technique of graph covers to determine the automorphism groups of uniform subset graphs Γ ( 2 k , k , k − 1 ) and Γ ( 2 k , k , 1 ) . The determination of automorphism groups answers a conjecture posed by Mark Ramras and Elizabeth Donovan. They conjectured that Aut ( Γ ( 2 k , k , k − 1 ) ) ≅ S 2 k × < T > , where T is the complementation map X ↦ T ( X ) = X c = { 1 , 2 , … , 2 k } ∖ X , and X is a k -subset of Ω = { 1 , 2 , … , 2 k } .

Authors:Hassan Ahmed; Akhlaq Ahmad Bhatti; Akbar Ali Abstract: Publication date: Available online 12 February 2018 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Hassan Ahmed, Akhlaq Ahmad Bhatti, Akbar Ali A connected graph G is said to be cactus if no two cycles of G have any common edge. The present note is devoted to developing some extremal results for the zeroth-order general Randić index of cactus graphs and finding some sharp bounds on this index.

Authors:Riyan Wicaksana Putra; Yeni Susanti Abstract: Publication date: Available online 12 February 2018 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Riyan Wicaksana Putra, Yeni Susanti Let G = ( V , E ) be a simple connected and undirected graph. Let f : V ∪ E → { 1 , 2 , … , k } be a total labeling of G . The weight of an edge u v is defined by w f ( u v ) = f ( u ) + f ( v ) + f ( u v ) . The labeling f is called an edge irregular total k -labeling if w f ( u v ) ≠ w f ( u ′ v ′ ) for any two distinct edges u v , u ′ v ′ . If G admits such a labeling, then the minimum k is called the total edge irregularity strength of G . In this paper we determine the total edge irregularity strength of centralized uniform theta graphs.

Authors:Faisal Susanto Abstract: Publication date: Available online 12 February 2018 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Faisal Susanto Let H and G be finite simple graphs where every edge of G belongs to at least one subgraph that is isomorphic to H . An ( a , d ) - H -antimagic total labeling of a graph G is a bijection f : V ( G ) ∪ E ( G ) → { 1 , 2 , … , V ( G ) + E ( G ) } such that for all subgraphs H ′ isomorphic to H , the H -weights, w ( H ′ ) = ∑ v ∈ V ( H ′ ) f ( v ) + ∑ u v ∈ E ( H ′ ) f ( u v ) form an arithmetic progression { a , a + d , … , a + ( k − 1 ) d } where a > 0 , d ≥ 0 are two fixed integers and k is the number of subgraphs of G isomorphic to H . Moreover, if the vertex set V ( G ) receives the minimum possible labels { 1 , 2 , … , V ( G ) } , then f is called a super ( a , d ) - H -antimagic total labeling. In this paper we study super ( a , d ) - C n -antimagic total labeling of a disconnected graph, namely m C n .

Authors:Mahdi Amani Abstract: Publication date: Available online 12 February 2018 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Mahdi Amani We introduce gaps that are edges or external pointers in AVL trees such that the height difference between the subtrees rooted at their two endpoints is equal to 2. Using gaps we prove the Basic-Theorem that illustrates how the size of an AVL tree (and its subtrees) can be represented by a series of powers of 2 of the heights of the gaps, this theorem is the first such simple formula to characterize the number of nodes in an AVL tree. Then, we study the extreme case of AVL trees, the perfectly unbalanced AVL trees, by introducing Fibonacci-isomorphic trees that are isomorphic to Fibonacci trees of the same height and showing that they have the maximum number of gaps in AVL trees. Note that two ordered trees (such as AVL trees) are isomorphic iff there exists a one-to-one correspondence between their nodes that preserves not only adjacency relations in the trees, but also the roots. In the rest of the paper, we study combinatorial properties of Fibonacci-isomorphic trees.

Authors:Purnima Gupta; Rajesh Singh Abstract: Publication date: Available online 3 February 2018 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Purnima Gupta, Rajesh Singh Given a graph G = ( V , E ) , not necessarily finite, a graphoidal cover of G means a collection Ψ of non-trivial paths in G called Ψ -edges, which are not necessarily open (not necessarily finite), such that every vertex of G is an internal vertex of at most one path in Ψ and every edge of G is in exactly one path in Ψ . The set of all graphoidal covers of a graph G = ( V , E ) is denoted by G G and for a given Ψ ∈ G G the ordered pair ( G , Ψ ) is called a graphoidally covered graph. Two vertices u and v of G are Ψ -adjacent if they are the ends of an open Ψ -edge. A set D of vertices in ( G , Ψ ) is Ψ -independent if no two vertices in D are Ψ -adjacent and is said to be Ψ -dominating if every vertex of G is either in D or is Ψ -adjacent to a vertex in D ; G is γ Ψ ( G ) -definable ( γ i Ψ ( G ) -definable) if ( G , Ψ ) has a finite Ψ -dominating ( Ψ -independent Ψ -dominating) set. Clearly, if G is γ i Ψ ( G ) -definable, then G is γ Ψ ( G ) -definable and γ Ψ ( G ) PubDate: 2018-02-26T18:40:01Z DOI: 10.1016/j.akcej.2018.01.002

Authors:C. Meenakshi; KM. Kathiresan Abstract: Publication date: Available online 3 February 2018 Source:AKCE International Journal of Graphs and Combinatorics Author(s): C. Meenakshi, KM. Kathiresan A k-magic labeling of a finite, simple graph with V ( G ) = p and E ( G ) = q , is a bijection from the set of edges into the integers { 1 , 2 , 3 , … , q } such that the vertex set V can be partitioned into k sets V 1 , V 2 , V 3 , … , V k , 1 ≤ k ≤ p , and each vertex in the set V i has the same vertex sum and any two distinct vertices in different sets have different vertex sum, where a vertex sum is the sum of the labels of all edges incident with that vertex. A graph is called k-magic if it has k -magic labeling, for some k , 1 ≤ k ≤ p . The study of k -magic labeling is interesting, since all magic graphs are 1-magic and all antimagic graphs are p -magic. In this paper, we discuss the k -magicness of the Complete bipartite graph K p , p , where 1 ≤ k ≤ 2 p .

Authors:Meenakshi P. Wasadikar; Karuna T. Gaikwad Abstract: Publication date: Available online 2 February 2018 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Meenakshi P. Wasadikar, Karuna T. Gaikwad We introduce the concepts of a primary and a 2-absorbing primary ideal and the radical of an ideal in a lattice. We study some properties of these ideals. A characterization for the radical of an ideal to be a primary ideal is given. Also a characterization for an ideal I to be a 2-absorbing primary ideal is proved. Examples and counter examples are given wherever necessary.

Authors:Bryan S. Hernandez; Virgilio P. Sison Abstract: Publication date: Available online 2 February 2018 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Bryan S. Hernandez, Virgilio P. Sison Let q = p r , p a prime, r a positive integer, and F q the Galois field with cardinality q and characteristic p . In this paper, we study some weight properties of rank-metric codes and subspace codes. The rank weight is not egalitarian nor homogeneous, and the rank weight distribution of M 2 ( F q ) is completely determined by the general linear group G L ( 2 , q ) . We consider subspace weight that is defined on subspace codes and examine their egalitarian property. We also present some examples of rank-metric codes endowed with the rank distance and Grassmannian codes endowed with the subspace distance. These codes were generated from left ideals of M 2 ( F p ) using idempotent elements of M 2 ( F p ) .

Authors:A.S. Khairnar; B.N. Waphare Abstract: Publication date: Available online 1 February 2018 Source:AKCE International Journal of Graphs and Combinatorics Author(s): A.S. Khairnar, B.N. Waphare We consider the ring Z n (integers modulo n ) with the partial order ‘ ≤ ’ given by ‘ a ≤ b if either a = b or a ≡ a b ( m o d n ) ’. In this paper, we obtain necessary and sufficient conditions for the poset ( Z n , ≤ ) to be a lattice.

Authors:R. Rajarajachozhan; R. Sampathkumar Abstract: Publication date: Available online 1 February 2018 Source:AKCE International Journal of Graphs and Combinatorics Author(s): R. Rajarajachozhan, R. Sampathkumar The Eulerian Cycle Decomposition Conjecture, by Chartrand, Jordon and Zhang, states that if the minimum number of odd cycles in a cycle decomposition of an Eulerian graph G of size m is a , the maximum number of odd cycles in such a cycle decomposition is b and ℓ is an integer such that a ≤ ℓ ≤ b where ℓ and m are of the same parity, then there is a cycle decomposition of G with exactly ℓ odd cycles. This conjecture is verified for the line graph of the complete graph.

Authors:S.A. Mane Abstract: Publication date: Available online 1 February 2018 Source:AKCE International Journal of Graphs and Combinatorics Author(s): S.A. Mane The connectivity of a graph is an important measurement for the fault-tolerance of the network. To provide more accurate measures for the fault-tolerance of networks than the connectivity, some generalizations of connectivity have been introduced. Let H be a connected subgraph of a graph G . A set F of a connected subgraph of G is called a subgraph cut of G if G − F is either connected or trivial. If further, each member of F is isomorphic to H , then F is called an H -structure cut of G. The H -structure connectivity κ ( G ; H ) of G is the minimum cardinality of an H -structure cut of G . In this paper we determine κ ( Q n ; H ) or its upper bound where Q n is the n -dimensional hypercube with n ≥ 4 and H is either Q m with m ≤ n − 2 or even cycle C l with l ≤ 2 n .

Authors:Morteza Faghani; Gyula O.H. Katona Abstract: Publication date: Available online 1 February 2018 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Morteza Faghani, Gyula O.H. Katona

Authors:Martin Bača; Muhammad Irfan; Joe Ryan; Andrea Semaničová-Feňovčíková; Dushyant Tanna Abstract: Publication date: Available online 20 January 2018 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Martin Bača, Muhammad Irfan, Joe Ryan, Andrea Semaničová-Feňovčíková, Dushyant Tanna For a graph G , an edge labeling f e : E ( G ) → { 1 , 2 , … , k e } and a vertex labeling f v : V ( G ) → { 0 , 2 , 4 , … , 2 k v } are called total k -labeling, where k = max { k e , 2 k v } . The total k -labeling is called an edge irregular reflexive k -labeling of the graph G , if for every two different edges x y and x ′ y ′ of G , one has w t ( x y ) = f v ( x ) + f e ( x y ) + f v ( y ) ≠ w t ( x ′ y ′ ) = f v ( x ′ ) + f e ( x ′ y ′ ) + f v ( y ′ ) . The minimum k for which the graph G has an edge irregular reflexive k -labeling is called the reflexive edge strength of G . In this paper we determine the exact value of the reflexive edge strength for cycles, Cartesian product of two cycles and for join graphs of the path and cycle with 2 K 2 .

Authors:Aisha Javed; Muhammad Kamran Jamil Abstract: Publication date: Available online 10 January 2018 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Aisha Javed, Muhammad Kamran Jamil For a simple graph G = ( V ( G ) , E ( G ) ) , this paper deals with the existence of an edge labeling χ : E ( G ) → { 0 , 1 , … , k − 1 } , 2 ≤ k ≤ E ( G ) , which induces a vertex labeling χ ∗ : V ( G ) → { 0 , 1 , … , k − 1 } in such a way that for each vertex v , assigns the label χ ( e 1 ) ⋅ χ ( e 2 ) ⋅ ⋯ ⋅ χ ( e n ) ( ( mod k ) ) , where e 1 , e 2 , … , e n are the edges incident to the vertex v . The labeling χ 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 and vertices with χ ( e ) = i and χ ∗ ( e ) = i , respectively. In this paper, we examine the existence of such labeling for rhombic grid graph.

Authors:Kukil Kalpa Rajkhowa; Helen K. Saikia Abstract: Publication date: Available online 5 January 2018 Source:AKCE International Journal of Graphs and Combinatorics Author(s): Kukil Kalpa Rajkhowa, Helen K. Saikia Let R be a commutative ring and M be a unital R -module. The intersection graph of submodules of M , denoted by G M , is the graph whose vertex set is the collection of all submodules of M and in which two distinct vertices A and B are adjacent if and only if A ∩ B ≠ 0 . In this paper the notion of essentiality of modules plays a vital role in the study of intersection graph of submodules of M . This notion gives a new dimension in characterizing the center of intersection graphs of submodules of M . We define mna (maximal non-adjacent) vertex in G M and observe some of its characteristics. The notion of complemented intersection graph exhibits some significant algebraic and graphical properties. Moreover, defining the concept of isolated center in G M we establish certain results related to mna vertex.

Authors:P. Roushini Leely Pushpam; M. Kamalam Abstract: Publication date: Available online 5 January 2018 Source:AKCE International Journal of Graphs and Combinatorics Author(s): P. Roushini Leely Pushpam, M. Kamalam Let G = ( V , E ) be a graph and f : V → { 0 , 1 , 2 } be a function. The weight of a vertex u ∈ V is f ( u ) and a vertex u with weight f ( u ) = 0 is said to be undefended with respect to f , if it is not adjacent to a vertex with positive weight. The function f is a weak Roman dominating function (WRDF) if each vertex u with f ( u ) = 0 is adjacent to a vertex v with f ( v ) > 0 such that the function f ′ : V → { 0 , 1 , 2 } defined by f ′ ( u ) = 1 , f ′ ( v ) = f ( v ) − 1 and f ′ ( w ) = f ( w ) if w ∈ V − { u , v } , has no undefended vertex. The weight of f is w ( f ) = ∑ v ∈ V f ( v ) . The weak Roman domination number, denoted by γ r ( G ) , is the minimum weight of a weak Roman dominating function on G . In this paper we examine the effects on γ r ( G ) when G is modified by deleting a vertex.

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