Authors:V. Yegnanarayanan Pages: 163 - 178 Abstract: Let p >= 3 be a positive integer and let k \in {1, 2, ..., p-1} \ \lfloor p/2 \rfloor. The generalized Petersen graph GP(p,k) has its vertex and edge set as V(GP(p, k)) = $\{u_i : i \in Zp\} \cup \{u_i^\prime : i \in Z_p\}$ and E(GP(p, k)) = $\{u_i u_{i+1} : i \in Z_p\} \cup \{u_i^\prime u_{i+k}^\prime \in Z_p\} \cup \{u_iu_i^\prime : i \in Z_p\}$. In this paper we probe its spectrum and determine the Estrada index, Laplacian Estrada index, signless Laplacian Estrada index, normalized Laplacian Estrada index, and energy of a graph. While obtaining some interesting results, we also provide relevant background and problems. PubDate: 2017-10-16 DOI: 10.5614/ejgta.2017.5.2.1 Issue No:Vol. 5, No. 2 (2017)

Authors:Suk J. Seo, Peter J. Slater Pages: 179 - 193 Abstract: A distinguishing set for a graph G = (V, E) is a dominating set D, each vertex $v \in D$ being the location of some form of a locating device, from which one can detect and precisely identify any given "intruder" vertex in V(G). As with many applications of dominating sets, the set $D$ might be required to have a certain property for <D>, the subgraph induced by D (such as independence, paired, or connected). Recently the study of independent locating-dominating sets and independent identifying codes was initiated. Here we introduce the property of open-independence for open-locating-dominating sets. PubDate: 2017-10-16 DOI: 10.5614/ejgta.2017.5.2.2 Issue No:Vol. 5, No. 2 (2017)

Authors:Mehdi Alaeiyan, Ayoob Mehrabani Pages: 194 - 206 Abstract: 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 A_1, A_2, ..., A_m such that, for all $ i,j \in \lbrace 1, ... , m \rbrace $, every vertex of A_i is adjacent to the same number of vertices, namely, a_{ij} vertices, of A_j. The matrix $A=(a_{ij})_{i,j\in \lbrace 1,... ,m\rbrace }$, is called the parameter matrix. We study the perfect 3-colorings (also known as the equitable partitions into three parts) of the cubic graphs of order 10. In particular, we classify all the realizable parameter matrices of perfect 3-colorings for the cubic graphs of order 10. PubDate: 2017-10-16 DOI: 10.5614/ejgta.2017.5.2.3 Issue No:Vol. 5, No. 2 (2017)

Authors:Hamed Ghasemian Zoeram, Daniel Yaqubi Pages: 207 - 211 Abstract: A vertex of degree one is called an end-vertex and the set of end-vertices of G is denoted by End(G). For a positive integer k, a tree T be called k-ended tree if $ End(T) \leq k$. In this paper, we obtain sufficient conditions for spanning k-trees of 3-regular connected graphs. We give a construction sequence of graphs satisfying the condition. At the end, we present a conjecture about spanning k-ended trees of 3-regular connected graphs. PubDate: 2017-10-16 DOI: 10.5614/ejgta.2017.5.2.4 Issue No:Vol. 5, No. 2 (2017)

Authors:Anak Agung Gede Ngurah, Rinovia Simanjuntak Pages: 212 - 220 Abstract: A graph G of order p and size q is called super edge-magic if there exists a bijective function f from V(G) U E(G) to {1, 2, 3, ..., p+q} such that f(x) + f(xy) + f(y) is a constant for every edge $xy \in E(G)$ and f(V(G)) = {1, 2, 3, ..., p}. The super edge-magic deficiency of a graph G is either the smallest nonnegative integer n such that G U nK_1 is super edge-magic or +~ if there exists no such integer n. In this paper, we study the super edge-magic deficiency of join product graphs. We found a lower bound of the super edge-magic deficiency of join product of any connected graph with isolated vertices and a better upper bound of the super edge-magic deficiency of join product of super edge-magic graphs with isolated vertices. Also, we provide constructions of some maximal graphs, ie. super edge-magic graphs with maximal number of edges. PubDate: 2017-10-16 DOI: 10.5614/ejgta.2017.5.2.5 Issue No:Vol. 5, No. 2 (2017)

Authors:Thodoris Karatasos, Evi Papaioannou Pages: 221 - 240 Abstract: In this work, we present an innovative image recognition technique which is based on the exploitation of transit-data in images or simple photographs of sites of interest. Our objective is to automatically transform real-world images to graphs and, then, compute Minimum Spanning Trees (MST) in them.We apply this framework and present an application which automatically computes efficient construction plans (for escalator or low-emission hot spots) for connecting all points of interest in cultural sites, i.e., archaeological sites, museums, galleries, etc, aiming to to facilitate global physical access to cultural heritage and artistic work and make it accessible to all groups of population. PubDate: 2017-10-16 DOI: 10.5614/ejgta.2017.5.2.6 Issue No:Vol. 5, No. 2 (2017)

Authors:Kijung Kim Pages: 241 - 246 Abstract: In 2010, Kim, Park and Sano studied the competition numbers of Johnson graphs. They gave the competition numbers of J(n,2) and J(n,3).In this note, we consider the competition number of J(n,4). PubDate: 2017-10-16 DOI: 10.5614/ejgta.2017.5.2.7 Issue No:Vol. 5, No. 2 (2017)

Authors:Steven Schluchter, J. Z. Schroeder Pages: 247 - 263 Abstract: A proper embedding of a graph G in a pseudosurface P is an embedding in which the regions of the complement of G in P are homeomorphic to discs and a vertex of G appears at each pinchpoint in P; we say that a proper embedding of G in P is self dual if there exists an isomorphism from G to its dual graph. We give an explicit construction of a self-dual embedding of the complete bipartite graph K_{4m,4n} in an orientable pseudosurface for all $m, n\ge 1$; we show that this embedding maximizes the number of umbrellas of each vertex and has the property that for any vertex v of K_{4m,4n}, there are two faces of the constructed embedding that intersect all umbrellas of v. Leveraging these properties and applying a lemma of Bruhn and Diestel, we apply a surgery introduced here or a different known surgery of Edmonds to each of our constructed embeddings for which at least one of m or n is at least 2. The result of these surgeries is that there exist distinct orientable and nonorientable pseudosurfaces with the same Euler characteristic that feature a self-dual embedding of K_{4m,4n}. PubDate: 2017-10-16 DOI: 10.5614/ejgta.2017.5.2.8 Issue No:Vol. 5, No. 2 (2017)

Authors:Radosław Cymer Pages: 264 - 275 Abstract: In decomposition theory, extreme sets have been studied extensively due to its connection to perfect matchings in a graph. In this paper, we first define extreme sets with respect to degree-matchings and next investigate some of their properties. In particular, we prove the generalized Decomposition Theorem and give a characterization for the set of all extreme vertices in a graph. PubDate: 2017-10-16 DOI: 10.5614/ejgta.2017.5.2.9 Issue No:Vol. 5, No. 2 (2017)

Authors:Kamal Lochan Patra, Binod Kumar Sahoo Pages: 276 - 303 Abstract: This paper is a survey on the upper and lower bounds for the largest eigenvalue of the Laplacian matrix, known as the Laplacian spectral radius, of a graph. The bounds are given as functions of graph parameters like the number of vertices, the number of edges, degree sequence, average 2-degrees, diameter, covering number, domination number, independence number and other parameters. PubDate: 2017-10-16 DOI: 10.5614/ejgta.2017.5.2.10 Issue No:Vol. 5, No. 2 (2017)

Authors:Bryan Freyberg, Melissa Keranen Pages: 304 - 311 Abstract: The following generalization of distance magic graphs was introduced in [2]. A directed Z_n-distance magic labeling of an oriented graph $\overrightarrow{G}=(V,A)$ of order n is a bijection $\overrightarrow{\ell}\colon V \rightarrow Z_n$ with the property that there is a $\mu \in Z_n$ (called the magic constant) such that w(x)= \sum_{y\in N_{G}^{+}(x)} \overrightarrow{\ell}(y) - \sum_{y\in N_{G}^{-}(x)} \overrightarrow{\ell}(y)= \mu$ for every x \in V(G). If for a graph G there exists an orientation $\overrightarrow{G}$ such that there is a directed Z_n-distance magic labeling $\overrightarrow{\ell}$ for $\overrightarrow{G}$, we say that G is orientable Z_n-distance magic and the directed Z_n-distance magic labeling $\overrightarrow{\ell}$ we call an orientable Z_n-distance magic labeling. In this paper, we find orientable Z_n-distance magic labelings of the Cartesian product of cycles. In addition, we show that even-ordered hypercubes are orientable Z_n-distance magic. PubDate: 2017-10-16 DOI: 10.5614/ejgta.2017.5.2.11 Issue No:Vol. 5, No. 2 (2017)

Authors:I Nengah Suparta Pages: 312 - 324 Abstract: A Gray code of length n is a list of all binary words of length n such that each two successive codewords differ in only one bit position. If the first and the last codewords also share this property, the Gray code is called cyclic, otherwise it is called non-cyclic. The numbers indicating bit positions in where two successive codewords differ in the list of Gray codes are called transition numbers, and the sequence of these all numbers is called the transition sequence of the Gray code. In this article, bit positions of a Gray code of length n will be counted from 1 up until n. If a graph with vertex set {1, 2, ..., n} having the property that two vertices i and j are adjacent in the graph if and only if, i and $j$ are consecutive transitions in the transition sequence of a Gray code, then the graph is called induced by the Gray code. Some classes of bipartite graphs are shown to be induced by Gray codes. Particularly, we show that complete bipartite graphs are induced by Gray codes. PubDate: 2017-10-16 DOI: 10.5614/ejgta.2017.5.2.12 Issue No:Vol. 5, No. 2 (2017)

Authors:Faraha Ashraf, Martin Baca, Andrea Semanicova-Fenovcikova, Ayesha Shabbir Pages: 325 - 334 Abstract: A simple graph G=(V(G),E(G)) admits an H-covering if every edge in E(G) belongs at least to one subgraph of G isomorphic to a given graph H. Then the graph G admitting H-covering admits an H-irregular total k-labeling f: V(G) U E(G) \to {1, 2, ..., k} if for every two different subgraphs H' and H'' isomorphic to H there is $wt_{f}(H') \neq wt_{f}(H'')$, where $wt_{f}(H)= \sum \limits_{v\in V(H)} f(v) + \sum \limits_{e \in E(H)} f(e)$ is the associated H-weight. The minimum k for which the graph G has an H-irregular total k-labeling is called the total H-irregularity strength of the graph G.In this paper, we obtain the precise value of the total H-irregularity strength of G-amalgamation of graphs. PubDate: 2017-10-16 DOI: 10.5614/ejgta.2017.5.2.13 Issue No:Vol. 5, No. 2 (2017)

Authors:Mustapha Aouchiche, Pierre Hansen Pages: 335 - 346 Abstract: The paper discusses bounds on the nullity number of graphs. It is proved in [B. Cheng and B. Liu, On the nullity of graphs. Electron. J. Linear Algebra 16 (2007) 60--67] that $\eta \le n - D$, where $\eta$, n and D denote the nullity number, the order and the diameter of a connected graph, respectively. We first give a necessary condition on the extremal graphs corresponding to that bound, and then we strengthen the bound itself using the maximum clique number. In addition, we prove bounds on the nullity using the number of pendant neighbors in a graph. One of those bounds is an improvement of a known bound involving the domination number. PubDate: 2017-10-16 DOI: 10.5614/ejgta.2017.5.2.14 Issue No:Vol. 5, No. 2 (2017)

Authors:Amrita Acharyya, Jon M Corson, Bikash Das Pages: 347 - 373 Abstract: We generalize the idea of cofinite groups, due to B. Hartley, [2]. First we define cofinite spaces in general. Then, as a special situation, we study cofinite graphs and their uniform completions.The idea of constructing a cofinite graph starts with defining a uniform topological graph $\Gamma$, in an appropriate fashion. We endow abstract graphs with uniformities corresponding to separating filter bases of equivalence relations with finitely many equivalence classes over $\Gamma$. It is established that for any cofinite graph there exists a unique cofinite completion. PubDate: 2017-10-16 DOI: 10.5614/ejgta.2017.5.2.15 Issue No:Vol. 5, No. 2 (2017)