Abstract: Publication date: Available online 22 March 2019Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Zbigniew R. Bogdanowicz Let G=Cn1□Cn2□⋯□Cnk be a Cartesian product of k≥2 directed cycles. It is known that G has a Hamilton cycle if there is a permutation (n1′,n2′,…,nk′) of (n1,n2,…,nk) that satisfies gcd(ni′,ni+1′⋅ni+2′⋯nk′)=si+zi and gcd(ni′,si)=gcd(ni+1′⋅ni+2′⋯nk′,zi)=1 for some positive integers si,zi, where k>i≥1. In addition, if gcd(n1′⋅n2′⋯nk′,s1⋅z1)=1 then G has two arc-disjoint Hamilton cycles. We identify a Hamilton cycle and two arc-disjoint Hamilton cycles in G in such cases.

Abstract: Publication date: Available online 21 March 2019Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Vahan V. Mkrtchyan, Gagik N. Vardanyan The classical Berge–Fulkerson conjecture states that any bridgeless cubic graph G admits a list of six perfect matchings such that each edge of G belongs to two of the perfect matchings from the list. In this short note, we discuss two statements that are consequences of this conjecture. The first of them states that for any bridgeless cubic graph G, edge e and i with 0≤i≤2, there are three perfect matchings F1,F2,F3 of G such that F1∩F2∩F3=0̸ and e belongs to exactly i of these perfect matchings. The second one states that for any bridgeless cubic graph G and its vertex v, there are three perfect matchings F1,F2,F3 of G such that F1∩F2∩F3=0̸ and the edges incident to v belong to k1, k2 and k3 of these perfect matchings, where the numbers k1, k2 and k3 satisfy the obvious necessary conditions. In the paper, we show that the first statement is equivalent to Fan–Raspaud conjecture. We also show that the smallest counter-example to the second one is a cyclically 4-edge-connected cubic graph.

Abstract: Publication date: Available online 20 March 2019Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Allan Bickle The vertex-arboricity aG of a graph G is the minimum number of subsets that the vertices of G can be partitioned so that the subgraph induced by each set of vertices is a forest. Kronk and Mitchem proved a generalization of Brooks’ Theorem for vertex arboricity, aG=1+12△G if and only if G is a cycle or a complete graph of odd order. We provide a short proof of this result using degeneracy.

Abstract: Publication date: Available online 19 March 2019Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): S.M. Hegde, Suresh Dara In 1972, Erdős–Faber–Lovász (EFL) conjectured that, if H is a linear hypergraph consisting of n edges of cardinality n, then it is possible to color the vertices with n colors so that no two vertices with the same color are in the same edge. In 1978, Deza, Erdös and Frankl had given an equivalent version of the same for graphs: Let G=⋃i=1nAi denote a graph with n complete graphs A1,A2, …,An, each having exactly n vertices and have the property that every pair of complete graphs has at most one common vertex, then the chromatic number of G is n. The clique degree dK(v) of a vertex v in G is given by dK(v)= {Ai:v∈V(Ai),1≤i≤n} . In this paper we give a method for assigning colors to the graphs satisfying the hypothesis of the Erdős–Faber–Lovász conjecture and every Ai (1≤i≤n) has atmost n2 vertices of clique degree greater than one using Symmetric latin Squares and clique degrees of the vertices of G.

Abstract: Publication date: Available online 19 March 2019Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Saeid Alikhani, Samaneh Soltani The distinguishing index of a graph G, denoted by D′(G), is the least number of labels in an edge coloring of G not preserved by any non-trivial automorphism. The distinguishing chromatic index χD′(G) of a graph G is the least number d such that G has a proper edge coloring with d labels that is preserved only by the identity automorphism of G. In this paper we compute the distinguishing chromatic index for some specific graphs. Also we study the distinguishing chromatic index of corona product and join of two graphs.

Abstract: Publication date: Available online 19 March 2019Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Subarsha Banerjee, Avishek Adhikari In this paper, we have studied Signless Laplacian spectrum of the power graph of finite cyclic groups. We have showed that n−2 is an eigen value of Signless Laplacian of the power graph of Zn,n≥2 with multiplicity at least ϕ(n). In particular, using the theory of Equitable Partitions, we have completely determined the Signless Laplacian spectrum of power graph of Zn for n=pq where p,q are distinct primes.

RH
(

Abstract: Publication date: Available online 14 March 2019Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Hortensia Galeana-Sánchez, Rocío Rojas-Monroy, Rocío Sánchez-López, Berta Zavala-Santana Let H be a digraph possibly with loops and D a digraph without loops whose arcs are colored with the vertices of H (D is said to be an H-colored digraph). A directed walk W in D is said to be an H-walk if and only if the consecutive colors encountered on W form a directed walk in H. A subset N of the vertices of D is said to be an H-kernel by walks if (1) for every pair of different vertices in N there is no H-walk between them and (2) for each vertex u in V(D)-N there exists an H-walk from u to N in D.Let H be a digraph and suppose that D is a digraph possibly infinite. In this paper we will work with the digraph RH(D), where RH(D) is an H-colored digraph defined as follows: V(RH(

Abstract: Publication date: Available online 13 March 2019Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Rebecca E. Garcia, Pamela E. Harris, Bethany Kubik, Shannon Talbott The generalized crown Snk is a well-known family of bipartite graphs whose order dimension is given in terms of the parameters n and k. In recent work, Garcia and Silva defined the notion of layering generalized crowns, producing multipartite posets called ℓ-layered generalized crowns, whose order dimension is easily determined using ℓ, n, and k. This paper extends the authors’ prior work on characterizing the associated graphs of critical pairs of generalized crowns, by providing a new and concrete description of an infinite family of graphs arising from critical pairs of the ℓ-layered generalized crowns. Our main result gives a characterization of the adjacency matrices of these graphs. Through their associated posets with computable order dimension, these graphs have a strict upper bound on their chromatic number.

Abstract: Publication date: Available online 13 March 2019Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): K.M. Koh, K.W. Soh We give a brief survey about the existing results on the power domination of the Cartesian product of graphs, and improve two of the results by determining the exact power domination numbers of two families of graphs, namely, the cylinder Pn□Cm and the tori Cn□Cm. We also establish the power domination number for Kn□K1,m, the Cartesian product of a complete graph and a star.

A
,+

Abstract: Publication date: Available online 13 March 2019Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Hortensia Galeana-Sánchez, Rocío Rojas-Monroy, Rocío Sánchez-López Let D = (V(D), A(D)) a digraph. Consider the set PD = {P : P is a non trivial finite directed path in D} and let A and ℬ two subsets of PD. A subset N of V(D) is said to be an (A, ℬ)-kernel of D if (1) for every subset {u, v} of N there exists no uv-directed path P such that P ∈ A (N is A-independent) and (2) for every vertex x in V(D)∖ N there exist y in

Abstract: Publication date: Available online 11 March 2019Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Amrita Acharyya, Bikash Das We defined group actions on cofinite graphs to characterize a unique way of uniformly topologizing an abstract group with profinite topology, induced by the cofinite graphs, so that the aforesaid action becomes uniformly equicontinuous.

Abstract: Publication date: Available online 7 March 2019Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): K. Selvakumar, V. Ramanathan The concept of the annihilating-ideal graph of a commutative ring was introduced by Behboodi et. al in 2011. In this paper, we extend this concept to the hypergraph for which we define an algebraic structure called k-annihilating-ideal of a commutative ring which is the vertex set of the hypergraph of such commutative ring. Let R be a commutative ring and k an integer greater than 2 and let A(R,k) be the set of all k-annihilating-ideals of R. The k-annihilating-ideal hypergraph of R, denoted by AGk(R), is a hypergraph with vertex set A(R,k), and for distinct elements I1,I2,…,Ik in A(R,k), the set {I1,I2,…,Ik} is an edge of AGk(R) if and only if ∏i=1kIi=(0) and the product of any (k−1) elements of the {I1,I2,…,Ik} is nonzero. In this paper, we provide a necessary and sufficient condition for the completeness of 3-annihilating-ideal hypergraph of a commutative ring. Further, we study the planarity of AG3(R) and characterize all commutative ring R whose 3-annihilating-ideal hypergraph AG3(R) is planar.

L
-intersecting+families&rft.title=AKCE+International+Journal+of+Graphs+and+Combinatorics&rft.issn=0972-8600&rft.date=&rft.volume=">Sunflowers and
L
-intersecting families

Abstract: Publication date: Available online 27 February 2019Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Gábor Hegedűs Let f(k,r,s) stand for the least number so that if F is an arbitrary k-uniform, L-intersecting set system, where L =s, and F has more than f(k,r,s) elements, then F contains a sunflower with r petals.We give an upper bound for f(k,3,s).

Abstract: Publication date: Available online 21 February 2019Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Bijon Biswas, Raibatak Sen Gupta, M.K. Sen, S. Kar The Square element graph over a semigroup S is a simple undirected graph Sq(S) whose vertex set consists precisely of all the non-zero elements of S, and two vertices a,b are adjacent if and only if either ab or ba belongs to the set {t2:t∈S}∖{1}, where 1 is the identity of the semigroup (if it exists). In this paper, we study the various properties of Sq(S). In particular, we concentrate on square element graphs over three important classes of semigroups. First, we consider the semigroup Ωn formed by the ideals of Zn. Afterwards, we consider the symmetric groups Sn and the dihedral groups Dn. For each type of semigroups mentioned, we look into the structural and other graph-theoretic properties of the corresponding square element graphs.

Abstract: Publication date: Available online 21 February 2019Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Bryan Freyberg Let G be an additive abelian group of order n and let n=a1+a2+...+ap be a partition of n where 1≤a1≤a2≤⋯≤ap. A constant sum partition (or t-sum partition) of G is a pairwise disjoint union of subsets A1,A2,…,Ap such that G=A1∪A2∪⋯∪Ap, Ai =ai, and ∑a∈Aia=t, for some fixed t∈G and every 1≤i≤p. In 2009, Kaplan, Lev, and Roditty proved that a 0-sum partition of the cyclic group Zn exists for n odd if and only if a2≥2. In this paper, we address the case when n is even. In particular, we show that a n2-sum partition of Zn exists for n even and p odd if and only if a2≥2. Moreover, we provide applications to distance magic-type graph...

Abstract: Publication date: Available online 21 February 2019Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Izak Broere, Johannes Heidema A graph property is a class of graphs which is closed under isomorphisms. Some properties are also closed under one or more specified constructions that extend any graph into a supergraph containing the original graph as an induced subgraph. We introduce and study in particular the concept that a property P “allows finite spiking” and show that there is a universal graph in every induced-hereditary property of finite character which allows finite spiking. We also introduce the concept that P “allows isolated vertex addition” and constructively show that there is a unique graph with the so-called P-extension property in every induced-hereditary property P of finite character which allows finite spiking and allows isolated vertex addition; such a graph is then universal in P too. Infinitely many examples which satisfy the conditions of both these results are obtained by taking the property of Kn-free graphs for an arbitrary integer n≥2.

Abstract: Publication date: Available online 17 January 2019Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): S. Pirzada, M. Aijaz, S.P. Redmond For a commutative ring R with non-zero zero divisor set Z∗(R), the zero divisor graph of R is Γ(R) with vertex set Z∗(R), where two distinct vertices x and y are adjacent if and only if xy=0. The upper dimension and the resolving number of a zero divisor graph Γ(R) of some rings are determined. We provide certain classes of rings which have the same upper dimension and metric dimension and give an example of a ring for which these values do not coincide. Further, we obtain some bounds for the upper dimension in zero divisor graphs of commutative rings and provide a subset of vertices which cannot be excluded from any resolving set.

Abstract: Publication date: Available online 12 December 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): M. Javaid Let G be a graph of order n and A(G)=[ai,j] be its adjacency matrix such that ai,j=1 if vi is adjacent to vj and ai,j=0 otherwise, where 1≤i,j≤n. In a certain family of graphs, a graph is called minimizing (or second minimizing) if the least eigenvalue of its adjacency matrix attains the minimum (or second minimum). In this paper, we characterize the second minimizing graph among all graphs which belong to the set of complements of the trees.

Abstract: Publication date: Available online 7 December 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Mehdi Alaeiyan, Ayoob Mehrabani Perfect coloring is a generalization of the notion of completely regular codes, given by Delsarte. A perfect m-coloring of a graph G with m colors is a partition of the vertex set of G into m parts A1, . . . , Am such that, for all i,j∈{1,…,m}, every vertex of Ai is adjacent to the same number of vertices, namely, aij vertices, of Aj . The matrix A=(aij)i,j∈{1,…,m}, is called the parameter matrix. We study the perfect 2-colorings (also known as the equitable partitions into two parts) of the cubic graphs of order less than or equal to 10. In particular, we classify all the realizable parameter matrices of perfect 2-colorings for the cubic graphs of order less than or equal to 10.

Abstract: Publication date: Available online 6 December 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): G. Sethuraman, M. Sujasree Rosa, in his classical paper (Rosa, 1967) introduced a hierarchical series of labelings called ρ,σ,β and α labeling as a tool to settle Ringel’s Conjecture which states that if T is any tree with q edges then the complete graph K2q+1 can be decomposed into 2q+1 copies of T. Inspired by the result of Rosa, many researchers significantly contributed to the theory of graph decomposition using graph labeling. In this direction, in 2004, Blinco, El-Zanati and Vanden Eynden introduced γ-labeling as a stronger version of ρ-labeling. A function h defined on the vertex set of a graph G with q edges is called a γ-labeling if(i) h is a ρ-labeling of G,(ii) G is tripartite with vertex tripartition (A,B,C) with C={c} and b̄∈B such that (b̄,c) is the unique edge joining an element of B to c,(iii) for every edge (a,v)∈E(G) with a∈A, h(a)

Abstract: Publication date: December 2018Source: AKCE International Journal of Graphs and Combinatorics, Volume 15, Issue 3Author(s): Koko K. Kayibi, S. Pirzada, T.A. Chishti Let Ω be the set of all m×n matrices, where ri and cj 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(ϵ)≤2cmax(mn)4ln(cmaxϵ−1),where cmax−1 is the maximal value in a cell.

Abstract: Publication date: December 2018Source: AKCE International Journal of Graphs and Combinatorics, Volume 15, Issue 3Author(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 Spec(G). In this paper, we introduce two new operations G1■k(G3□G2) and (G4□G1)■k(G3□G2), and describe the adjacency spectra of G1■k(G3□G2) and (G4□G1)■k(G3□G2) of regular graphs G1, G2 and arbitrarily graphs G3, G4 in terms of their adjacency spectra. As the applications, we obtain some new integral spectrum graphs.

Abstract: Publication date: December 2018Source: AKCE International Journal of Graphs and Combinatorics, Volume 15, Issue 3Author(s): Wenhui Ma, Guanghua Dong, Yingyu Lu, Ning Wang A graph with q edges is called antimagic 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 K2 is antimagic. In this paper, through a labeling method and a modification on this labeling, we obtained that the lexicographic product graphs Pm[Pn] are antimagic.

Abstract: Publication date: December 2018Source: AKCE International Journal of Graphs and Combinatorics, Volume 15, Issue 3Author(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.

Abstract: Publication date: December 2018Source: AKCE International Journal of Graphs and Combinatorics, Volume 15, Issue 3Author(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.

Abstract: Publication date: December 2018Source: AKCE International Journal of Graphs and Combinatorics, Volume 15, Issue 3Author(s): Sylwia Cichacz, Irmina A. Zioło Let G=(V,E) be a graph, by V2, 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⊂V2∖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.

Abstract: Publication date: December 2018Source: AKCE International Journal of Graphs and Combinatorics, Volume 15, Issue 3Author(s): Rikio Ichishima, Akito Oshima The beta-number of a graph G is the smallest positive integer n for which there exists an injective function f:VG→0,1,…,n such that each uv∈EG is labeled fu−fv and the resulting set of edge labels is c,c+1,…,c+ EG −1 for some positive integer c. The beta-number of G is +∞, otherwise. If c=1, then the resulting beta-number is called the strong beta-number of G. A linear forest is a forest for which each component is a path. In this paper, we determine a formula for the (strong) beta-number of the linear forests with two components. This leads us to a partial formula for the beta-number of the disjoint union of multiple copies of the same linear forests.

Abstract: Publication date: December 2018Source: AKCE International Journal of Graphs and Combinatorics, Volume 15, Issue 3Author(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 ZN(R)∗, and two vertices x and y are adjacent if and only if xy is nilpotent, where ZN(R)={x∈R:xyis nilpotent, for somey∈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.

Abstract: Publication date: December 2018Source: AKCE International Journal of Graphs and Combinatorics, Volume 15, Issue 3Author(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 Brn and prove that tes(Brn)=(5n−3)∕3, while tvs(Brn)=(n+1)∕3.

Abstract: Publication date: December 2018Source: AKCE International Journal of Graphs and Combinatorics, Volume 15, Issue 3Author(s): Ivan Gutman, Boris Furtula, Vladimir Katanić The Randić index RG 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 RG, namely its connection with the degree-based information content of a (molecular) graph. This connection is based on the linear correlation betweenRG and the logarithm of the multiplicative version of the Randić index.

Abstract: Publication date: Available online 22 November 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Ali Zeydi Abdian, Lowell W. Beineke, Mohanmmad Reza Oboudi, Afshin Behmaram, Krishnaiyan Thulasiraman, Saeid Alikhani, Kewen Zhao In this study we investigate the spectra of the family of connected multicone graphs. A multicone graph is defined to be the join of a clique and a regular graph. Let r, t and s be natural numbers, and let Kr denote a complete graph on r vertices. It is proved that connected multicone graphs Kr▽sKt, a natural generalization of friendship graphs, are determined by their adjacency spectra as well as their Laplacian spectra. Also, we show that the complement of multicone graphs Kr▽sKt is determined by their adjacency spectra, where s≠2.

Abstract: Publication date: Available online 20 November 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Muhammad Kamran Siddiqui, Muhammad Imran, Muhammad Ibrahim In this paper we define a totally irregular total labeling for Cartesian and strong product of two paths, which is at the same time vertex irregular total labeling and also edge irregular total labeling. More preciously, we determine the exact value of the total irregularity strength for Cartesian and strong product of two paths.

Abstract: Publication date: Available online 6 November 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Teresa W. Haynes, Jason T. Hedetniemi, Stephen T. Hedetniemi, Alice McRae, Nicholas Phillips Let G=(V,E) be a graph. For two disjoint sets of vertices R and S, set R dominates set S if every vertex in S is adjacent to at least one vertex in R. In this paper we introduce the upper domatic number D(G), which equals the maximum order k of a vertex partition π={V1,V2,…,Vk} such that for every i,j, 1≤i

Abstract: Publication date: Available online 11 October 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Shilpa T. Bhangale, Madhukar M. Pawar In this paper we compute isolate domination number and independent domination number of some well known classes of graphs. Also a counter example is provided, which disprove the result on independent domination for Euler Totient Cayley graph proved by Uma Maheswari and B. Maheswari and improved it for some sub cases.

Abstract: Publication date: Available online 9 October 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Saad Ihsan Butt, Muhammad Numan, Sharafat Ali, Andrea Semaničová-Feňovčíková In this paper we deal with the problem of labeling the vertices, edges and faces of a toroidal Tnm and Klein bottle Knm grid graphs with mn 4-sided faces by the consecutive integers from 1 up to V(Tnm) + E(Tnm) + F(Tnm) and V(Knm) + E(Knm) + F(Knm) in such a way that the label of a 4-sided face and the labels of the vertices and edges surrounding that face all together add up to a weight of that face. These face-weights then form an arithmetic progression with common difference d. The paper examines the existence of such labelings for several differences d.

Abstract: Publication date: Available online 8 October 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): M. Torktaz, A.R. Ashrafi Let G be a finite group. The commuting graph Γ=C(G) is a simple graph with vertex set G and two vertices are adjacent if and only if they commute with each other. In this paper, the normalized and signless Laplacian spectra of the commuting graphs of certain classes of finite groups are computed.

Abstract: Publication date: Available online 2 October 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): L. Yahyaei, S.A. Katre A k-labeling of a graph is a labeling of vertices of the graph by k-tuples of non-negative integers in such a way that two vertices of G are adjacent if and only if their label k-tuples differ in each coordinate. The dimension of a graph G is the least k such that G has a k-labeling.In this paper we obtain the dimension of a lobster or close bounds for it in various cases.

Abstract: Publication date: Available online 2 October 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Magda Dettlaff, Magdalena Lemańska, Jerzy Topp, Radosław Ziemann, Paweł Żyliński Imagine that we are given a set D of officials and a set W of civils. For each civil x∈W, there must be an official v∈D that can serve x, and whenever any such v is serving x, there must also be another civil w∈W that observes v, that is, w may act as a kind of witness, to avoid any abuse from v. What is the minimum number of officials to guarantee such a service, assuming a given social network'In this paper, we introduce the concept of certified domination that models the aforementioned problem. Specifically, a dominating set D of a graph G=(VG,EG) is said to be certified if every vertex in D has either zero or at least two neighbours in VG∖D. The cardinality of a minimum certified dominating set in G is called the certified domination number of G. Herein, we present the exact values of the certified domination number for some classes of graphs as well as provide some upper bounds on this parameter for arbitrary graphs. We then characterise a wide class of graphs with equal domination and certified domination numbers and characterise graphs with large values of certified domination numbers. Next, we examine the effects on the certified domination number when the graph is modified by deleting/adding an edge or a vertex. We also provide Nordhaus–Gaddum type inequalities for the certified domination number.

Abstract: Publication date: Available online 18 September 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Harishchandra S. Ramane, Ashwini S. Yalnaik, Reza Sharafdini The status of a vertex u, denoted by σG(u), is the sum of the distances between u and all other vertices in a graph G. The first and second status connectivity indices of a graph G are defined as S1(G)=∑uv∈E(G)[σG(u)+σG(v)] and S2(G)=∑uv∈E(G)σG(u)σG(v) respectively, where E(G) denotes the edge set of G. In this paper we have defined the first and second status co-indices of a graph G as S1¯(G)=∑uv∉E(G)[σG(u)+σG(v)] and S2¯(G)=∑uv∉E(G)σG(u)σG(v) respectively. Relations between status connectivity indices and status co-indices are established. Also these indices are computed for intersection graph, hypercube, Kneser graph and achiral polyhex nanotorus.

Abstract: Publication date: Available online 17 September 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Martin Bača, Muhammad Irfan, Andrea Semaničová-Feňovčíková For a simple graph G=(V,E) with the vertex set V and the edge set E and for an integer k, 2≤k≤ E(G) , an edge labeling φ:E(G)→{0,1,…,k−1} induces a vertex labeling φ∗:V(G)→{0,1,…,k−1} defined by φ∗(v)=φ(e1)⋅φ(e2)⋅…⋅φ(en)(modk), where e1,e2,…,en 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

Abstract: Publication date: Available online 14 September 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Beatriz Carely Luna-Olivera, Criel Merino, Marcelino Ramírez-Ibáñez The connection between the matching polynomial and the chromatic polynomial for triangle-free graphs was revealed in the work of Farrell and Whitehead. We extend this result to all graph by mirroring the corresponding result of Godsil and Gutman for the acyclic polynomial and the characteristic polynomial. We also reintroduce the clique polynomial of Farrell as an evaluation of the U-polynomial of Noble and Welsh, which also happens to contain the matching and chromatic polynomials.

r
-partite+self-complementary+and+almost+self-complementary+

Abstract: Publication date: Available online 14 September 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): L.N. Kamble, C.M. Deshpande, B.P. Athawale A hypergraph H is said to be r-partite r-uniform if its vertex set V can be partitioned into non-empty sets V1,V2,...,Vr so that every edge in the edge set E(H), consists of precisely one vertex from each set Vi, i=1,2,…,r. It is denoted as Hr(V1,V2,…,Vr) or H(n1,n2,…,nr)r if Vi =ni for i=1,2,…r. In this paper we define r-partite self-complementary and almost self-complementary r-uniform hypergraph. We prove that, there exists an r-partite self-complementary r-uniform hypergraph Hr(V1,V2,…,Vr) where Vi =ni for i=1,2,…,r if and only if at least one of n1,n2,…,nr is even. And we prove that, there exists an

Abstract: Publication date: Available online 31 August 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Moein Pourbaba, Habib Azanchiler, Ghodratolah Azadi In this article, we construct a submodular function using the rank function of a matroid and study induced matroid with constructed polymatroid, then we relate some properties of connectivity of new matroid with the main matroid.

Abstract: Publication date: Available online 31 August 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Saeid Alikhani, Samaneh Soltani The distinguishing number (index) D(G) (D′(G)) of a graph G is the least integer d such that G has a vertex labeling (edge labeling) with d labels that is preserved only by a trivial automorphism. A graphoidal cover of G is a collection ψ of (not necessarily open) paths in G such that every path in ψ has at least two vertices, 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 ψ. Let Ω(G,ψ) denote the intersection graph of ψ. A graph H is called a graphoidal graph, if there exist a graph G and a graphoidal cover ψ of G such that H≅Ω(G,ψ). In this paper, we study the distinguishing number and the distinguishing index of the line graph and the graphoidal graph of a simple connected graph G.

Abstract: Publication date: Available online 30 August 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Dushyant Tanna, Joe Ryan, Andrea Semaničová-Feňovčíková, Martin Bača For a graph G we define k-labeling ρ such that the edges of G are labeled with integers {1,2,…,ke} and the vertices of G are labeled with even integers {0,2,…,2kv}, where k=max{ke,2kv}. The labeling ρ is called a vertex irregular reflexive k-labeling if distinct vertices have distinct weights, where the vertex weight is defined as the sum of the label of that vertex and the labels of all edges incident this vertex. The smallest k for which such labeling exists is called the reflexive vertex strength of G.In this paper, we give exact values of reflexive vertex strength for prisms, wheels, fan graphs and baskets.

Abstract: Publication date: Available online 29 August 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Kiyoshi Hosono, Masatsugu Urabe A k-hole of a planar point set in general position is a convex k-gon whose vertices are elements of the set and whose interior contains no elements of the set. We discuss the minimum size of a point set that contains specified holes with disjoint interiors.

Abstract: Publication date: Available online 16 August 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Y.M. Borse, J.B. Saraf Let G be a graph obtained by taking the Cartesian product of finitely many cycles. It is known that G is bipancyclic, that is, G contains cycles of every even length from 4 to V(G) . We extend this result for the existence of 3-regular subgraphs in G. We prove that G contains a 3-regular, 2-connected subgraph with l vertices if l=8 or l=12 or l is an even integer with 16≤l≤ V(G) . For l∈{6,10,14}, we give necessary and sufficient conditions for the existence of such subgraphs in G.

F
-domination+in+graphs&rft.title=AKCE+International+Journal+of+Graphs+and+Combinatorics&rft.issn=0972-8600&rft.date=&rft.volume=">On
F
-domination in graphs

Abstract: Publication date: Available online 16 August 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Manju Raju, Kiran R. Bhutani, Babak Moazzez, S. Arumugam Let G=(V,E) be a graph and let F be a family of subsets of V such that ⋃F∈FF=V. A dominating set D of G is called an F-dominating set if D∩F≠∅ for all F∈F. The minimum cardinality of an F-dominating of G is called the F-domination number of G and is denoted by γF(G). In this paper we present several basic results on this parameter. We also introduce the concept of F-irredundance and obtain an inequality chain four parameters.

Abstract: Publication date: Available online 14 August 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): D. Sarala, Hanyuan Deng, C. Natarajan, S.K. Ayyaswamy For a molecular graph, the first Zagreb index of a graph is equal to the sum of squares of the vertex degrees of the graph and the forgotten topological index (F-index) of a graph is defined as the sum of cubes of the vertex degrees of the graph. These parameters have applications in chemistry and drug structures. In this paper, we study the F index of strong product of two connected graphs in which one of the graphs is obtained by using four new sums called F sums of graphs and the other is any connected graph.

(4K2,P3)
-minimal+graphs&rft.title=AKCE+International+Journal+of+Graphs+and+Combinatorics&rft.issn=0972-8600&rft.date=&rft.volume=">On Ramsey
(
4
K
2
,
P
3
)
-minimal graphs

Abstract: Publication date: August 2018Source: AKCE International Journal of Graphs and Combinatorics, Volume 15, Issue 2Author(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 ℛ(4K2,H), for any connected graph H. Moreover, we give a relation between Ramsey (4K2,P3)- and (3K2,P3)-minimal graphs, and Ramsey (4K2,P3)- and (2K2,P3)-minimal graphs. Furthermore, we determine all graphs in ℛ(4K2,P3).

Abstract: Publication date: August 2018Source: AKCE International Journal of Graphs and Combinatorics, Volume 15, Issue 2Author(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,W5) for n≥7, where θn is the set of theta graphs of order n and W5 is the wheel graph of order 5.

Abstract: Publication date: August 2018Source: AKCE International Journal of Graphs and Combinatorics, Volume 15, Issue 2Author(s): P. Kaemawichanurat, T. Jiarasuksakun A k-γc-critical graph is a graph G with connected domination number γc(G)=k and γc(G+uv)

Abstract: Publication date: August 2018Source: AKCE International Journal of Graphs and Combinatorics, Volume 15, Issue 2Author(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(n1.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)+3k.

Abstract: Publication date: August 2018Source: AKCE International Journal of Graphs and Combinatorics, Volume 15, Issue 2Author(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.

Abstract: Publication date: August 2018Source: AKCE International Journal of Graphs and Combinatorics, Volume 15, Issue 2Author(s): Yoshimi Egawa, Keiko Kotani, Shunsuke Nakamura Let G be a 4-connected graph, and let Ẽ(G) denote the set of those edges of G which are not contained in a triangle, and let Ec(G) denote the set of 4-contractible edges of G. We show that if 3≤ Ẽ(G) ≤4 or Ẽ(G) ≥7, then Ec(G) ≥( Ẽ(G) +8)∕4 unless G has one of the three specified configurations.

Abstract: Publication date: August 2018Source: AKCE International Journal of Graphs and Combinatorics, Volume 15, Issue 2Author(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.

Abstract: Publication date: August 2018Source: AKCE International Journal of Graphs and Combinatorics, Volume 15, Issue 2Author(s): Sergei Chernyi 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.

Abstract: Publication date: August 2018Source: AKCE International Journal of Graphs and Combinatorics, Volume 15, Issue 2Author(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.

Abstract: Publication date: August 2018Source: AKCE International Journal of Graphs and Combinatorics, Volume 15, Issue 2Author(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.

Abstract: Publication date: August 2018Source: AKCE International Journal of Graphs and Combinatorics, Volume 15, Issue 2Author(s): K. Pattabiraman The inverse sum indeg index ISI(G) of a simple graph G is defined as the sum of the terms dG(u)dG(v)dG(u)+dG(v) over all edges uv of G, where dG(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.

Abstract: Publication date: Available online 30 July 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Gaidhani Y.S., Deshpande C.M., Pirzada S. Semigraph is a generalization of graph. We introduce the concept of energy in a semigraph in two ways, one, the matrix energy Em, as summation of singular values of the adjacency matrix of a semigraph, and the other, polynomial energy Ere, as energy of the characteristic polynomial of the adjacency matrix. We obtain some bounds for Em and show that Em is never a square root of an odd integer and Ere cannot be an odd integer. We investigate matrix energy of a partial semigraph and change in the matrix energy due to edge deletion.

Abstract: Publication date: Available online 19 July 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Omid Khormali The distinguishing number of graphs is generalized in two directions by Cheng and Cowen (local distinguishing number) and Collins and Trenk (Distinguishing chromatic number). In this paper, we define and study the local distinguishing chromatic number of graphs. The exact values of 1-local distinguishing chromatic number of several classes of graphs such as stars, complete graphs, complete bipartite graphs, Petersen graph, cycles and paths are computed. Moreover, several bounds for local distinguishing chromatic number are presented.

Abstract: Publication date: Available online 18 July 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Priyavrat Deshpande, Kavita Sutar A toric arrangement is a finite collection of codimension-1 subtori in a torus. The intersections of these subtori stratify the ambient torus into faces of various dimensions. The incidence relations among these faces give rise to many interesting combinatorial problems. One such problem is to obtain a closed-form formula for the number of faces in terms of the intrinsic arrangement data. In this paper we focus on toric arrangements defined by crystallographic root systems. Such an arrangement is equipped with an action of the associated Weyl group. The main result is a formula that expresses the face numbers in terms of a sum of indices of certain subgroups of this Weyl group.

Abstract: Publication date: Available online 17 July 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Shanmuga Vadivu Andiyappan, Muthusamy Appu For an integer λ, G(λ) denotes a graph G with uniform edge-multiplicity λ. Let J be a subset of positive integers. A 2-regular subgraph of m-partite graph Km⊗In containing vertices of all but one partite set is called partial 2-factor, where ⊗ denotes wreath product and In is an independent set on n vertices. If (Km⊗In)(λ) can be partitioned into edge-disjoint partial 2-factors such that each partial 2-factor consists of cycles of lengths from J, then we say that (Km⊗In)(λ) has a (J,λ)-cycle frame. The Oberwolfach problem OP (m1α1,m2α2,…,mtαt), raised by Ringel, asks the existence of a 2-factorization of Kn (when n is odd) or Kn−I (when n is even), in which each 2-factor consists of exactly αi cycles of length mi, i=1,2,…,t. In this paper, we show that there exists a

Abstract: Publication date: Available online 12 July 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): I. Tarawneh, R. Hasni, A. Ahmad For a simple graph G, a vertex labeling ϕ:V(G)→{1,2,…,k} is called a vertex k-labeling. For any edge xy in G, its weight wϕ(xy)=ϕ(x)+ϕ(y). If all the edge weights are distinct, then ϕ is called an edge irregular k-labeling of G. The minimum k for which the graph G has an edge irregular k-labeling is called the edge irregularity strength of G, denoted by es(G).In this paper, we determine an exact value of edge irregularity strength for triangular grid graph Lnm, zigzag graph Znm and Cartesian product Pn□Pm□P2.

Abstract: Publication date: Available online 7 July 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Ali Zeydi Abdian, Afshin Behmaram, Gholam Hossein Fath-Tabar In the past decades, graphs that are determined by their spectrum have received more attention, since they have been applied to several fields, such as randomized algorithms, combinatorial optimization problems and machine learning. An important part of spectral graph theory is devoted to determining whether given graphs or classes of graphs are determined by their spectra or not. So, finding and introducing any class of graphs which are determined by their spectra can be an interesting and important problem. A graph is said to be DQS if there is no other non-isomorphic graph with the same signless Laplacian spectrum. For a DQS graph G, we show that G∪rK1∪sK2 is DQS under certain conditions, where r, s are natural numbers and K1 andK2 denote the complete graphs on one vertex and two vertices, respectively. Applying these results, some DQS graphs with independent edges and isolated vertices are obtained.

Abstract: Publication date: Available online 2 July 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Manoj Changat, Prasanth G. Narasimha-Shenoi, Geetha Seethakuttyamma Betweenness is a universal notion present in several disciplines of mathematics. The notion of betweenness has a profound history and many pioneers like Euclid, Pasch, Hilbert have studied betweenness axiomatically. In discrete mathematics too, betweenness is present and several authors have worked on this concept from an axiomatic view. In graph theory, betweenness is developed mainly as metric betweenness, studied using the shortest path metric in a connected graph, thus resulting in the notion of the interval function. Many interesting results are available in graph theory using the interval function. The interval function is generalized to induced path function by replacing shortest paths by induced paths. The induced path betweenness also captured attention among graph theorists with several interesting results to date. From an axiomatic point of view, two pertinent questions can be framed on these functions. Is it possible to axiomatically characterize the interval function of some special graphs using some set of first order axioms defined on an arbitrary transit function' Is it possible to characterize the graphs with the help of their interval functions' In this paper, we survey the results as answers to these questions available from the research papers.

Abstract: Publication date: Available online 28 June 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Martin Kochol Generalized Tutte–Grothendieck invariants are mappings from the class of matroids to a commutative ring that are characterized recursively by contraction–deletion rules. Well known examples are Tutte, chromatic, tension and flow polynomials. In general, the rule consists of three formulas valid separately for loops, isthmuses, and the ordinary elements. We show that each generalized Tutte–Grothendieck invariant thus also Tutte polynomials on matroids can be transformed so that the contraction–deletion rule for loops (isthmuses) coincides with the general case.

Abstract: Publication date: Available online 27 June 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Srinivasa Rao Kola, Balakrishna Gudla, Niranjan P.K. An L2,1-coloring of a simple connected graph G is an assignment of non-negative integers to the vertices of G such that adjacent vertices color difference is at least two, and vertices that are at distance two from each other get different colors. The maximum color assigned in an L2,1-coloring is called span of that coloring. The span of a graph G denoted by λG is the smallest span taken over all L2,1-colorings of G. A hole is an unused color within the range of colors used by the coloring. An L2,1-coloring f is said to be irreducible if no other L2,1-coloring can be produced by decreasing a color of f. The maximum number of holes of a graph G, denoted by HλG, is the maximum number of holes taken over all irreducible L2,1-colorings with span λG. Laskar and Eyabi (Christpher, 2009) conjectured that if T is a tree, then HλT=2 if and only if T=Pn, n>4. We show that this conjecture does not hold by providing a counterexample. Also, we give some classes of trees with maximum number of holes two.

Abstract: Publication date: Available online 25 June 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Danny Dyer, Sadegheh Haghshenas, Nabil Shalaby In 1978, Huang and Rosa solved the spectrum problem for decomposition for trees with up to eight edges. Also, the packing and covering problems were settled for trees with up to six edges by Roditty. In this paper, we find the spectrum of excess graphs for trees with up to four edges. Moreover, we use new techniques in our proofs and state lemmas that will be useful for generalizing our result for trees with higher number of edges.

Abstract: Publication date: Available online 23 June 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): P. Ragukumar, G. Sethuraman The binomial tree B0 consists of a single vertex. The binomial tree Bk is an ordered tree defined recursively. The binomial tree Bk consists of two binomial trees Bk−1 that are linked together: the root of one is the leftmost child of the root of the other. The popular Graceful Tree Conjecture states that every tree is graceful. In this paper, we show that binomial trees Bk is graceful for every k≥0.

Abstract: Publication date: Available online 20 June 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Y.M. Borse, A.V. Sonawane, S.R. Shaikh An H-factorization of a graph G is a partition of the edge set of G into spanning subgraphs (or factors) each of whose components are isomorphic to a graph H. Let G be the Cartesian product of the cycles C1,C2,…,Cn with Ci =2ki≥4 for each i. El-Zanati and Eynden proved that G has a C-factorization, where C is a cycle of length s, if and only if s=2t with 2≤t≤k1+k2+⋯+kn. We extend this result to get factorizations of G into m-regular, m-connected and bipancyclic subgraphs. We prove that for 2≤m

Abstract: Publication date: Available online 20 June 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): L. Hamidian Jahromi, A. Abbasi Let R be a commutative ring with a proper ideal I. A generalization of total graph is introduced and investigated. It is the (undirected) graph with all elements of R as vertices, that two distinct vertices x,y∈R are adjacent if and only if x+y∈SH(I) where SH(I)={a∈R:ra∈I for some r∈H} and H is a multiplicatively closed subset of R. This version of total graph is denoted by T(ΓHI(R)). We in addition characterize certain lower and upper bounds for the genus of the total graph, and compute genus T(ΓHI(R)) on finite ring R, with respect to some special ideal I.

Abstract: Publication date: Available online 20 June 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): James M. Hammer, Joshua Harrington Let G=V,E be a simple graph. A dominating set D⊆V is a set such that the closed neighborhood of D is the entire vertex set. An independence set of a graph G is a subset of vertices that are pairwise non-adjacent. A DI-pathological graph is a graph where every minimum dominating set intersects every maximal independent set. Let d(G,i) denote the number of dominating sets of G of size i. The domination polynomial of a graph G is defined by D(G,x)=∑i=γ(G)Vd(G,i)xi. Let s(G,i) denote the number of independent sets of size i in a graph G. The independence polynomial is defined by I(G,x)=∑i=0α(G)s(G,i)xi. In this paper, we will examine the domination polynomial and the independence polynomial of a family of extremal DI-pathological graphs. We will further define an independent dominating set and examine the corresponding independent domination polynomial for these graphs.

Abstract: Publication date: Available online 19 June 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Ivan Gutman, Emina Milovanović, Igor Milovanović The two Zagreb indices M1=∑vd(v)2 and M2=∑uvd(u)d(v) are vertex-degree-based graph invariants that have been introduced in the 1970s and extensively studied ever since. In the last few years, a variety of modifications of M1 and M2 were put forward. The present survey of these modified Zagreb indices outlines their main mathematical properties, and provides an exhaustive bibliography.

Abstract: Publication date: Available online 18 June 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): T.K. Mathew Varkey, John K. Rajan Energy of a graph is defined as the sum of the absolute values of the eigenvalues of the adjacency matrix A(G) of a graph G and is denoted by E(G). The graph G with n vertices is called nonhypoenergetic if E(G)≥n and hypoenergetic if E(G)0. In this paper we study about nonhypoenergetic and hypoenergetic graphs among singular graphs. We also construct singular graphs of larger nullity using coalescence.

Abstract: Publication date: Available online 25 May 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): S.S. Rukmani, J. Prema, V. Vijayalakshmi Let {H(n,m)} be the family of graphs where H(n,m) is obtained from the complete graph Kn by removing the edges of m vertex disjoint copies of triangles. In this paper, we determine the multiplicity of triangles in any two coloring of the edges of H(n,m) when n−3m≥8.

Abstract: Publication date: Available online 5 May 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Avinash Patil, B.N. Waphare In this paper, we introduce a partial order on rings with involution, which is a generalization of the partial order on the set of projections in a Rickart ∗-ring. We prove that a ∗-ring with the natural partial order forms a sectionally semi-complemented poset. It is proved that every interval [0,x] forms a Boolean algebra in case of abelian Rickart ∗-rings. The concepts of generalized comparability (GC) and partial comparability (PC) are extended to involve all the elements of a ∗-ring. Further, it is proved that these concepts are equivalent in finite abelian Rickart ∗-rings.

Abstract: Publication date: Available online 14 March 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Qingyun Tao, Yaoping Hou A graph G is said to be borderenergetic (L-borderenergetic, respectively) if its energy (Laplacian energy, respectively) equals the energy (Laplacian energy, respectively) of the complete graph Kn. We extend this concept to signless Laplacian energy of a graph. A graph G is called Q-borderenergetic if its signless Laplacian energy is same as that of the complete graph Kn, i.e., QE(G)=QE(Kn)=2n−2. In this paper, we construct some infinite family of graphs satisfying QE(G)=LE(G)=2n−2, this happens to give a positive answer to the open problem mentioned by Nair Abreu et al. in Nair Abreu et al. (2011), that is whether there are connected non-bipartite, non-regular graphs satisfying QE(G)=LE(G). We also obtain some bounds on the order and size of Q-borderenergetic graphs. Finally, we use a computer search to find out all Q-borderenergetic graphs on no more than 10 vertices, the number of such graphs is 39.

Abstract: Publication date: Available online 9 March 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Shriram K. Nimbhorkar, Deepali B. Banswal Some generalizations of the concept of a supplemented lattice, namely a soc-supplemented-lattice, soc-amply-supplemented-lattice, soc-weak-supplemented-lattice, soc-⊕-supplemented-lattice and completely soc-⊕-supplemented-lattice are introduced. Various results are proved to show the relationship between these lattices. We have also proved that, if L is a soc-⊕-supplemented-lattice satisfying the summand intersection property (SIP), then L is a completely soc-⊕-supplemented-lattice.

Abstract: Publication date: Available online 21 February 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(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 lc(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 Qn for every n.

Abstract: Publication date: Available online 21 February 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(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.

Abstract: Publication date: Available online 13 February 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(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 ith copy of H at the vertex o to the ith 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 vw∈E(H), or ab∈E(L) and v=w=o. Let G=L▹H and P2▹H⊆G, the graph G is said to be an (a,d)-P2▹H-antimagic total graph if there exists a bijective function f:V(G)∪

Abstract: Publication date: Available online 12 February 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(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.

Abstract: Publication date: Available online 3 February 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(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 V1,V2,V3,…,Vk,1≤k≤p, and each vertex in the set Vi 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 Kp,p, where 1≤k≤2p.

Abstract: Publication date: Available online 2 February 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(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.

Abstract: Publication date: Available online 2 February 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Bryan S. Hernandez, Virgilio P. Sison Let q=pr, p a prime, r a positive integer, and Fq 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 M2(Fq) is completely determined by the general linear group GL(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 M2(Fp) using idempotent elements of M2(Fp).

Abstract: Publication date: Available online 1 February 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(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.

Z
n
&rft.title=AKCE+International+Journal+of+Graphs+and+Combinatorics&rft.issn=0972-8600&rft.date=&rft.volume=">Generalized projections in
Z
n

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

Abstract: Publication date: Available online 20 January 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(s): Martin Bača, Muhammad Irfan, Joe Ryan, Andrea Semaničová-Feňovčíková, Dushyant Tanna For a graph G, an edge labeling fe:E(G)→{1,2,…,ke} and a vertex labeling fv:V(G)→{0,2,4,…,2kv} are called total k-labeling, where k=max{ke,2kv}. The total k-labeling is called an edge irregular reflexive k-labeling of the graph G, if for every two different edges xy and x′y′ of G, one has wt(xy)=fv(x)+fe(xy)+fv(y)≠wt(x′y′)=fv(x′)+fe(x′y′)+fv(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 2K2.

Abstract: Publication date: Available online 10 January 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(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 χ(e1)⋅χ(e2)⋅⋯⋅χ(en)((modk)), where e1,e2,…,en 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

Abstract: Publication date: Available online 5 January 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(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 weightf(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∈Vf(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.

Abstract: Publication date: Available online 5 January 2018Source: AKCE International Journal of Graphs and CombinatoricsAuthor(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 GM, 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 GM 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 GM we establish certain results related to mna vertex.