cover
Filter by Year
Electronic Journal of Graph Theory and Applications (EJGTA)
ISSN : -     EISSN : -
The Electronic Journal of Graph Theory and Applications (EJGTA) is a refereed journal devoted to all areas of modern graph theory together with applications to other fields of mathematics, computer science and other sciences. The journal is published by the Indonesian Combinatorial Society (InaCombS), Graph Theory and Applications (GTA) Research Group - The University of Newcastle - Australia, and Faculty of Mathematics and Natural Sciences - Institut Teknologi Bandung (ITB) Indonesia. Subscription to EJGTA is free. Full-text access to all papers is available for free. All research articles as well as surveys and articles of more general interest are welcome. All papers will be refereed in the normal manner of mathematical journals to maintain the highest standards. This journal is sponsored by CARMA (Computer-Assisted Research Mathematics and its Applications) Priority Research Centre - The University of Newcastle - Australia, and Study Program of Information System- University of Jember - Indonesia.
Articles
129
Articles
On regular handicap graphs of order $n equiv 0$ mod 8

Froncek, Dalibor ( Department of Mathematics and Statistics, University of Minnesota Duluth Duluth, USA ) , Shepanik, Aaron ( Department of Mathematics and Statistics, University of Minnesota Duluth Duluth, USA )

Electronic Journal of Graph Theory and Applications (EJGTA) Vol 6, No 2 (2018): Electronic Journal of Graph Theory and Applications
Publisher : GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB

Show Abstract | Original Source | Check in Google Scholar |

Abstract

A handicap distance antimagic labeling of a graph G = (V, E) with n vertices is a bijection f̂ : V → {1, 2, …, n} with the property that f̂(xi) = i, the weight w(xi) is the sum of labels of all neighbors of xi, and the sequence of the weights w(x1), w(x2), …, w(xn) forms an increasing arithmetic progression. A graph G is a handicap distance antimagic graph if it allows a handicap distance antimagic labeling. We construct r-regular handicap distance antimagic graphs of order $n equiv 0 pmod{8}$ for all feasible values of r.

Interlace polynomials of friendship graphs

Eubanks-Turner, Christina ( Department of Mathematics, Loyola Marymount University, 90045 USA ) , Li, Aihua ( Department of Mathematical Sciences, Montclair State University, 07043 USA )

Electronic Journal of Graph Theory and Applications (EJGTA) Vol 6, No 2 (2018): Electronic Journal of Graph Theory and Applications
Publisher : GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB

Show Abstract | Original Source | Check in Google Scholar |

Abstract

In this paper, we study the interlace polynomials of friendship graphs, that is, graphs that satisfy the Friendship Theorem given by Erdös, Rényi and Sos. Explicit formulas, special values and behavior of coefficients of these polynomials are provided. We also give the interlace polynomials of other similar graphs, such as, the butterfly graph.

On distance signless Laplacian spectrum and energy of graphs

Alhevaz, Abdollah ( Shahrood University of Technology ) , Baghipur, Maryam ( Shahrood University of Technology ) , Hashemi, Ebrahim ( Shahrood University of Technology )

Electronic Journal of Graph Theory and Applications (EJGTA) Vol 6, No 2 (2018): Electronic Journal of Graph Theory and Applications
Publisher : GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB

Show Abstract | Original Source | Check in Google Scholar |

Abstract

The distance signless Laplacian spectral radius of a connected graph G is the largest eigenvalue of the distance signless Laplacian matrix of G‎, ‎defined as ‎D‎Q(G) = Tr(G) + D(G)‎, ‎where D(G) is the distance matrix of G and Tr(G) is the diagonal matrix of vertex transmissions of G‎. ‎In this paper we determine some upper and lower bounds on the distance signless Laplacian spectral radius of G based on its order and independence number‎, ‎and characterize the extremal graph‎. ‎In addition‎, ‎we give an exact description of the distance signless Laplacian spectrum and the distance signless Laplacian energy of the join of regular graphs in terms of their adjacency spectrum‎.

The structure of graphs with forbidden induced $C_4$, $overline{C}_4$, $C_5$, $S_3$, chair and co-chair

Ghazal, Salman ( Department of Mathematics, Faculty of Sciences I, Lebanese University, Beirut - Lebanon )

Electronic Journal of Graph Theory and Applications (EJGTA) Vol 6, No 2 (2018): Electronic Journal of Graph Theory and Applications
Publisher : GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB

Show Abstract | Original Source | Check in Google Scholar |

Abstract

We find the structure of graphs that have no C4, $overline{C}_4$, C5, S3, chair and co-chair as induced subgraphs. Then we deduce the structure of the graphs having no induced C4, $overline{C_4}$, S3, chair and co-chair and the structure of the graphs G having no induced C4, $overline{C_4}$ and such that every induced P4 of G is contained in an induced C5 of G.

Graphs, friends and acquaintances

Dalfo, Cristina ( Universitat Politecnica de Catalunya ) , Fiol, Miquel Àngel ( Universitat Politecnica de Catalunya )

Electronic Journal of Graph Theory and Applications (EJGTA) Vol 6, No 2 (2018): Electronic Journal of Graph Theory and Applications
Publisher : GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB

Show Abstract | Original Source | Check in Google Scholar |

Abstract

A graph is a mathematical object modeling the existence of a certain relation between pairs of elements of a given set. Many of the first results concerning graphs made reference to relationships between groups of people. In this article, we comment on four results of this kind: the Handshake lemma (related to graph colorings and Boolean algebra), a lemma on known and unknown people at a cocktail party (to Ramsey theory), a theorem on friends in common (to distance-regularity and coding theory), and Halls Marriage theorem (to the theory of networks). These four areas of graph theory, often with problems which are easy to state but difficult to solve, are extensively developed and currently give rise to much research work. As examples of representative problems and results of these areas we may cite the following: the Four Colors Theorem (4CTC), the Ramsey numbers, problems of the existence of distance-regular graphs and completely regular codes, and finally the study of topological proprieties of interconnection networks.

Color code techniques in rainbow connection

Septyanto, Fendy ( Departments of Mathematics, Faculty of Mathematics and Natural Sciences, Universitas Indonesia, Depok, Indonesia ) , Sugeng, Kiki A. ( Departments of Mathematics, Faculty of Mathematics and Natural Sciences, Universitas Indonesia, Depok, Indonesia )

Electronic Journal of Graph Theory and Applications (EJGTA) Vol 6, No 2 (2018): Electronic Journal of Graph Theory and Applications
Publisher : GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB

Show Abstract | Original Source | Check in Google Scholar |

Abstract

Let G be a graph with an edge k-coloring γ : E(G) → {1, …, k} (not necessarily proper). A path is called a rainbow path if all of its edges have different colors. The map γ is called a rainbow coloring if any two vertices can be connected by a rainbow path. The map γ is called a strong rainbow coloring if any two vertices can be connected by a rainbow geodesic. The smallest k for which there is a rainbow k-coloring (resp. strong rainbow k-coloring) on G is called the rainbow connection number (resp. strong rainbow connection number) of G, denoted rc(G) (resp. src(G)). In this paper we generalize the notion of “color codes” that was originally used by Chartrand et al. in their study of the rc and src of complete bipartite graphs, so that it now applies to any connected graph. Using color codes, we prove a new class of lower bounds depending on the existence of sets with common neighbours. Tight examples are discussed, involving the amalgamation of complete graphs, generalized wheel graphs, and a special class of sequential join of graphs.

Domination number of the non-commuting graph of finite groups

Vatandoost, Ebrahim ( Department of Mathematics, Faculty of Science, Imam Khomeini International University, Qazvin, Iran ) , Khalili, Masoumeh ( Department of Mathematics, Faculty of Science, Imam Khomeini International University, Qazvin, Iran )

Electronic Journal of Graph Theory and Applications (EJGTA) Vol 6, No 2 (2018): Electronic Journal of Graph Theory and Applications
Publisher : GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB

Show Abstract | Original Source | Check in Google Scholar |

Abstract

Let G be a non-abelian group. The non-commuting graph of group G, shown by ΓG, is a graph with the vertex set G Z(G), where Z(G) is the center of group G. Also two distinct vertices of a and b are adjacent whenever ab ≠ ba. A set S ⊆ V(Γ) of vertices in a graph Γ is a dominating set if every vertex v ∈ V(Γ) is an element of S or adjacent to an element of S. The domination number of a graph Γ denoted by γ(Γ), is the minimum size of a dominating set of Γ. </p><p>Here, we study some properties of the non-commuting graph of some finite groups. In this paper, we show that $gamma(Gamma_G)&lt;frac{|G|-|Z(G)|}{2}.$ Also we charactrize all of groups G of order n with t = ∣Z(G)∣, in which $gamma(Gamma_{G})+gamma(overline{Gamma}_{G})in {n-t+1,n-t,n-t-1,n-t-2}.$

Parsimonious edge-coloring on surfaces

Belcastro, Sarah-Marie ( Mathematical Staircase, Inc., Holyoke MA, and Smith College, Northampton MA, U.S.A. )

Electronic Journal of Graph Theory and Applications (EJGTA) Vol 6, No 2 (2018): Electronic Journal of Graph Theory and Applications
Publisher : GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB

Show Abstract | Original Source | Check in Google Scholar |

Abstract

We correct a small error in a 1996 paper of Albertson and Haas, and extend their lower bound for the fraction of properly colorable edges of planar subcubic graphs that are simple, connected, bridgeless, and edge-maximal to other surface embeddings of subcubic graphs.

Characterization of perfect matching transitive graphs

Zhou, Ju ( Department of Mathematics Kutztown University of Pennsylvania Kutztown, PA 19530 USA )

Electronic Journal of Graph Theory and Applications (EJGTA) Vol 6, No 2 (2018): Electronic Journal of Graph Theory and Applications
Publisher : GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB

Show Abstract | Original Source | Check in Google Scholar |

Abstract

A graph G is perfect matching transitive, shortly PM-transitive, if for any two perfect matchings M and N of G, there is an automorphism f : V(G) ↦ V(G) such that fe(M) = N, where fe(uv) = f(u)f(v). In this paper, the author proposed the definition of PM-transitive, verified PM-transitivity of some symmetric graphs, constructed several families of PM-transitive graphs which are neither vertex-transitive nor edge-transitive, and discussed PM-transitivity of generalized Petersen graphs.

On total edge product cordial labeling of fullerenes

Baca, Martin ( Department of Applied Mathematics and Informatics, Technical University, Kosice, Slovak Republic ) , Irfan, Muhammad ( Abdus Salam School of Mathematical Sciences, GC University, Lahore, Pakistan ) , Javed, Aisha ( Abdus Salam School of Mathematical Sciences, GC University, Lahore, Pakistan ) , Semanicova-Fenovcikova, Andrea ( Department of Applied Mathematics and Informatics, Technical University, Kosice, Slovak Republic )

Electronic Journal of Graph Theory and Applications (EJGTA) Vol 6, No 2 (2018): Electronic Journal of Graph Theory and Applications
Publisher : GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB

Show Abstract | Original Source | Check in Google Scholar |

Abstract

For a simple graph G = (V, E) 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 $varphi(e_1)cdotvarphi(e_2)cdotldotscdot varphi(e_n) pmod k$, 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 le i &lt; j le k-1$, where eφ(i) and vφ * (i) is the number of edges and vertices with φ(e) = i and φ * (v) = i, respectively. The paper examines the existence of such labelings for toroidal fullerenes and for Klein-bottle fullerenes.