cover
Contact Name
-
Contact Email
-
Phone
-
Journal Mail Official
-
Editorial Address
-
Location
,
INDONESIA
Electronic Journal of Graph Theory and Applications (EJGTA)
ISSN : 23382287     EISSN : -     DOI : -
Core Subject : Engineering,
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.
Arjuna Subject : -
Articles 382 Documents
Magic labeling on graphs with ascending subgraph decomposition Pancahayani, Sigit; Simanjuntak, Rinovia; Uttunggadewa, Saladin
Electronic Journal of Graph Theory and Applications (EJGTA) Vol 12, No 2 (2024): Electronic Journal of Graph Theory and Applications
Publisher : GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.5614/ejgta.2024.12.2.4

Abstract

Let t and q be positive integers that satisfy C(t + 1,2) ≤ q < C(t + 2,2) and let G be a simple and finite graph of size q. G is said to have ascending subgraph decomposition (ASD) if G can be decomposed into t subgraphs H1,H2,…,Ht without isolated vertices such that Hi is isomorphic to a proper subgraph of Hi+1 for 1 ≤ i ≤ t - 1, where {E(H1),…,E(Ht)} is a partition of E(G). A graph that admits an ascending subgraph decomposition is called an ASD graph.In this paper, we introduce a new type of magic labeling based on the notion of ASD. Let G be an ASD graph and f : V (G) ∪E(G) →{1,2,…,|V (G)| + |E(G)|} be a bijection. The weight of a subgraph Hi (1 ≤ i ≤ n) is w(Hi) = ∑ v∈V (Hi)f(v) + ∑ e∈E(Hi)f(e). If the weight of each ascending subgraph is constant, say w(Hi) = k, ∀ 1 ≤ i ≤ t, then f is called an ASD-magic labeling of G and G is called an ASD-magic graph. We present general properties of ASD-magic graphs and characterize certain classes of them.
Computational complexity of the police officer patrol problem on weighted digraphs Tomisawa, Masaki; Tohyama, Hiroaki
Electronic Journal of Graph Theory and Applications (EJGTA) Vol 12, No 2 (2024): Electronic Journal of Graph Theory and Applications
Publisher : GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.5614/ejgta.2024.12.2.10

Abstract

A vertex cover of a graph is a set of vertices that includes at least one endpoint of every edge of the graph and can be regarded as the placement of police officers or fixed surveillance cameras so that each street of a neighborhood represented by the graph can be confirmed visually without moving from their position. Given a graph G and a natural number k, the vertex cover problem is the problem of deciding whether there exists a vertex cover in G of size at most k. The vertex cover problem is one of Karp’s 21 NP-complete problems.Recently, we introduced an edge routing problem that a single police officer must confirm all the streets. The officer is allowed to move, but can confirm any street visually from an incident intersection without traversing it. We showed that the problem of deciding whether there exists a patrol route for a given mixed graph in which each edge is either traversed exactly once or confirmed visually is NP-complete. In this paper, we show that the police officer patrol problem remains NP-complete even if given graphs are weighted digraphs.
Steiner radial number resulting from various graph operations Gurusamy, R.; Lakshmanan, R.; Ratha Jeyalakshmi, R.; Arockiaraj, S.
Electronic Journal of Graph Theory and Applications (EJGTA) Vol 13, No 1 (2025): Electronic Journal of Graph Theory and Applications
Publisher : GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.5614/ejgta.2025.13.1.3

Abstract

The Steiner n-radial graph of a graph G on p vertices, denoted by SRn(G), has the vertex set as in G and any n(2 ≤ n ≤ p) vertices are mutually adjacent in SRn(G) if and only if they are n-radial in G. When G is disconnected, any n vertices are mutually adjacent in SRn(G) if not all of them are in the same component. For the edge set of SRn(G), draw Kn corresponding to each set of n-radial vertices. The Steiner radial number rS(G) of a graph G is the least positive integer n such that the Steiner n-radial graph of G is complete. In this paper, Steiner radial number has been determined for the line graph of any tree, total graph of any tree, complement of any tree, sum of two non-trivial trees and Mycielskians of some families. For any pair of positive integers a, b ≥ 3 with a ≤ b, there exists a graph whose Steiner radial number is a and Steiner radial number of its line graph is b.
Further results on the total vertex irregularity strength of trees Susanto, Faisal; Simanjuntak, Rinovia; Baskoro, Edy Tri
Electronic Journal of Graph Theory and Applications (EJGTA) Vol 13, No 1 (2025): Electronic Journal of Graph Theory and Applications
Publisher : GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.5614/ejgta.2025.13.1.9

Abstract

We investigate the total vertex irregularity strength of trees with specific characteristics. Initially, we categorize trees into three distinct groups: types A, B, and C. Subsequently, we calculate tvs(T) for all type A trees T where the maximum degree is at least three. Additionally, we provide the value of tvs(T) whenever T is a tree of types B or C with maximum degree at least three and large number of exterior vertices. Finally, we propose a conjecture related to tvs(T) where T is a non-path tree of types B or C with few exterior vertices. 
Doubly resolving number of the corona product graphs Jannesari, Mohsen
Electronic Journal of Graph Theory and Applications (EJGTA) Vol 13, No 1 (2025): Electronic Journal of Graph Theory and Applications
Publisher : GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.5614/ejgta.2025.13.1.15

Abstract

Two vertices u, v in a connected graph G are doubly resolved by vertices x, y of G if d(v, x)−d(u, x)≠d(v, y)−d(u, y). A set W of vertices of the graph G is a doubly resolving set for G if every two distinct vertices of G are doubly resolved by some two vertices of W. Doubly resolving number of a graph G, denoted by ψ(G), is the minimum cardinality of a doubly resolving set for G. In this paper, using adjacency resolving sets and dominating sets of graphs, we study doubly resolving sets in the corona product of graphs G and H, G ⊙ H. First, we obtain the upper and lower bounds for the doubly resolving number of the corona product G ⊙ H in terms of the order of G and the adjacency dimension of H, then we present several conditions that make each of these bounds feasible for the doubly resolving number of G ⊙ H. Also, for some important families of graphs, we obtain the exact value of the doubly resolving number of the corona product. 
On (super) edge-magic deficiency of some classes of graphs Ngurah, Anak Agung Gede; Simanjuntak, Rinovia; Baskoro, Edy Tri
Electronic Journal of Graph Theory and Applications (EJGTA) Vol 13, No 1 (2025): Electronic Journal of Graph Theory and Applications
Publisher : GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.5614/ejgta.2025.13.1.4

Abstract

A graph G of order p and size q is called edge-magic total if there exists a bijection ϕ from V(G)∪E(G) to the set {1, 2, …, p + q} such that ϕ(s)+ϕ(st)+ϕ(t) is a constant for every edge st in E(G). An edge-magic total graph with ϕ(V(G)) = {1, 2, …, p} is called super edge-magic total. Furthermore, the edge-magic deficiency of a graph G is the smallest integer n ≥ 0 such that G ∪ nK1 is edge-magic total. The super edge-magic deficiency of a graph G is either the smallest integer n ≥ 0 such that G ∪ nK1 is super edge-magic total or +∞ if there exists no such integer n. In this paper, we study the (super) edge-magic deficiency of join product graphs and 2-regular graphs.
Hamiltonicity in directed Toeplitz graphs Tn⟨1, 3, 6; t⟩ Malik, Shabnam
Electronic Journal of Graph Theory and Applications (EJGTA) Vol 13, No 1 (2025): Electronic Journal of Graph Theory and Applications
Publisher : GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.5614/ejgta.2025.13.1.10

Abstract

A directed Toeplitz graph, denoted as Tn⟨s1, …, sk; t1, …, tl⟩ of order n, is a digraph in which an edge (i,  j) exists if and only if j − i = sp or i − j = tq for some 1 ≤ p ≤ k and 1 ≤ q ≤ l. The adjacency matrix of such a graph forms a Toeplitz matrix, characterized by constant values along all diagonals parallel to the main diagonal. In this paper, we explore the Hamiltonicity of directed Toeplitz graphs of the form Tn⟨1, 3, 6; t⟩. We establish that Tn⟨1, 3, 6; t⟩ is Hamiltonian for t = 5, 10 and for all t ≥ 12, for every n. Additionally, we show that the graph remains Hamiltonian for all n, with only a finite number of exceptions when t = 3, 4, 6, 7, 8, 9 and 11. Specifically, for t = 1, the graph is Hamiltonian only when n = 7, while for t = 2, it is Hamiltonian under certain conditions on n, namely when n ≡ 0, 1, 3 (mod 4). 
On list coloring with separation of the complete graph and set system intersections Godin, Jean-Christophe; Grisot, Rémi; Togni, Olivier
Electronic Journal of Graph Theory and Applications (EJGTA) Vol 13, No 1 (2025): Electronic Journal of Graph Theory and Applications
Publisher : GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.5614/ejgta.2025.13.1.5

Abstract

We consider the following list coloring with separation problem: Given a graph G and integers a, b, find the largest integer c such that for any list assignment L of G with |L(v)| = a for any vertex v and |L(u)∩L(v)| ≤ c for any edge uv of G, there exists an assignment φ of sets of integers to the vertices of G such that φ(u)⊂L(u) and |φ(v)| = b for any vertex u and φ(u)∩φ(v)=∅ for any edge uv. Such a value of c is called the separation number of (G, a, b). Using a special partition of a set of lists for which we obtain an improved version of Poincaré’s crible, we determine the separation number of the complete graph Kn for some values of a, b and n, and prove bounds for the remaining values.
Connected size Ramsey numbers of matchings versus a small path or cycle Wang, Sha; Song, Ruyu; Zhang, Yixin; Zhang, Yanbo
Electronic Journal of Graph Theory and Applications (EJGTA) Vol 13, No 1 (2025): Electronic Journal of Graph Theory and Applications
Publisher : GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.5614/ejgta.2025.13.1.11

Abstract

Given two graphs G1, G2, the connected size Ramsey number rc(G1, G2) is defined to be the minimum number of edges of a connected graph G, such that for any red-blue edge colouring of G, there is either a red copy of G1 or a blue copy of G2. Concentrating on rc(nK2, G2) where nK2 is a matching, we generalise and improve two previous results as follows. Vito, Nabila, Safitri, and Silaban (J. Phys. Conf. Ser., 2021) obtained the exact values of rc(nK2, P3) for n = 2, 3, 4. We determine its exact values for all positive integers n. Rahadjeng, Baskoro, and Assiyatun (Proc. Indian Acad. Sci.: Math. Sci., 2017) proved that rc(nK2, C4)≤5n − 1 for n ≥ 4. We improve the upper bound from 5n − 1 to ⌊(9n − 1)/2⌋. In addition, we show a result which has the same flavour and has exact values: rc(nK2, C3)=4n − 1 for all positive integers n.
On arrowhead and diamond diameters Désérable, Dominique
Electronic Journal of Graph Theory and Applications (EJGTA) Vol 13, No 1 (2025): Electronic Journal of Graph Theory and Applications
Publisher : GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.5614/ejgta.2025.13.1.6

Abstract

Arrowhead and diamond form a family of two hierarchical Cayley graphs defined on the triangular grid. In their undirected version, they are isomorphic and merely define two distinct representations of the same graph. This paper gives the expression of their diameter, in the oriented and non–oriented case. It also displays the full distribution of antipodals. This family could appear as a promising topology for Network–on–Chip architectures.

Filter by Year

2013 2025


Filter By Issues
All Issue Vol 13, No 2 (2025): Electronic Journal of Graph Theory and Applications Vol 13, No 1 (2025): Electronic Journal of Graph Theory and Applications Vol 12, No 2 (2024): Electronic Journal of Graph Theory and Applications Vol 12, No 1 (2024): Electronic Journal of Graph Theory and Applications Vol 11, No 2 (2023): Electronic Journal of Graph Theory and Applications Vol 11, No 1 (2023): Electronic Journal of Graph Theory and Applications Vol 10, No 2 (2022): Electronic Journal of Graph Theory and Applications Vol 10, No 1 (2022): Electronic Journal of Graph Theory and Applications Vol 9, No 2 (2021): Electronic Journal of Graph Theory and Applications Vol 9, No 1 (2021): Electronic Journal of Graph Theory and Applications Vol 8, No 2 (2020): Electronic Journal of Graph Theory and Applications Vol 8, No 1 (2020): Electronic Journal of Graph Theory and Applications Vol 7, No 2 (2019): Electronic Journal of Graph Theory and Applications Vol 7, No 1 (2019): Electronic Journal of Graph Theory and Applications Vol 6, No 2 (2018): Electronic Journal of Graph Theory and Applications Vol 6, No 1 (2018): Electronic Journal of Graph Theory and Applications Vol 5, No 2 (2017): Electronic Journal of Graph Theory and Applications Vol 5, No 1 (2017): Electronic Journal of Graph Theory and Applications Vol 4, No 2 (2016): Electronic Journal of Graph Theory and Applications Vol 4, No 1 (2016): Electronic Journal of Graph Theory and Applications Vol 3, No 2 (2015): Electronic Journal of Graph Theory and Applications Vol 3, No 1 (2015): Electronic Journal of Graph Theory and Applications Vol 2, No 2 (2014): Electronic Journal of Graph Theory and Applications Vol 2, No 1 (2014): Electronic Journal of Graph Theory and Applications Vol 1, No 2 (2013): Electronic Journal of Graph Theory and Applications Vol 1, No 1 (2013): Electronic Journal of Graph Theory and Applications More Issue