cover
Article Per Year (5 Year)
All
Home Page
OAI Link
Editorial Team
Contact
Reviewer
Google Scholar
Contact Name
-
Contact Email
-
Phone
-
Journal Mail Official
-
Editorial Address
-
Location
,
INDONESIA
Electronic Journal of Graph Theory and Applications (EJGTA)
Published by Indonesian Combinatorial Society
ISSN : 23382287     EISSN : -     DOI : -
Core Subject : Engineering,
Electrical & Electronics 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
 5   6   7   8   9 
Efficient maximum matching algorithms for trapezoid graphs Phan-Thuan Do; Ngoc-Khang Le; Van-Thieu Vu
Electronic Journal of Graph Theory and Applications (EJGTA) Vol 5, No 1 (2017): 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.2017.5.1.2

Abstract

Trapezoid graphs are intersection graphs of trapezoids between two horizontal lines. Many NP-hard problems can be solved in polynomial time if they are restricted on trapezoid graphs. A matching in a graph is a set of pairwise disjoint edges, and a maximum matching is a matching of maximum size. In this paper, we first propose an $O(n(\log n)^3)$ algorithm for finding a maximum matching in trapezoid graphs, then improve the complexity to $O(n(\log n)^2)$. Finally, we generalize this algorithm to a larger graph class, namely $k$-trapezoid graphs. To the best of our knowledge, these are the first efficient maximum matching algorithms for trapezoid graphs.
Metric dimension of fullerene graphs Shehnaz Akhter; Rashid Farooq
Electronic Journal of Graph Theory and Applications (EJGTA) Vol 7, No 1 (2019): 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.2019.7.1.7

Abstract

A resolving set W is a set of vertices of a graph G(V, E) such that for every pair of distinct vertices u, v ∈ V(G), there exists a vertex w ∈ W satisfying d(u, w) ≠ d(v, w). A resolving set with minimum number of vertices is called metric basis of G. The metric dimension of G, denoted by dim(G), is the minimum cardinality of a resolving set of G. In this paper, we consider (3, 6)-fullerene and (4, 6)-fullerene graphs and compute the metric dimension for these fullerene graphs. We also give conjecture on the metric dimension of (3, 6)-fullerene and (4, 6)-fullerene graphs.
On the balanced case of the Brualdi-Shen conjecture on 4-cycle decompositions of Eulerian bipartite tournaments Rafael Del Valle Vega
Electronic Journal of Graph Theory and Applications (EJGTA) Vol 3, No 2 (2015): 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.2015.3.2.7

Abstract

The Brualdi-Shen Conjecture on Eulerian Bipartite Tournaments states that any such graph can be decomposed into oriented 4-cycles. In this article we prove the balanced case of the mentioned conjecture. We show that for any $2n\times 2n$ bipartite graph $G=(U\cup V, E)$ in which each vertex has $n$-neighbors with biadjacency matrix $M$ (or its transpose) there is a proper edge coloring of a column permutation of $M$ denoted $M^{\sigma}$ in which the nonzero entries of each of the $first$ $n$ columns are colored with elements from the set $\{n+1, n+2, \ldots, 2n\}$ and the nonzero entries of each of the $last$  $n$ columns are colored with elements from the set $\{1, 2, \ldots, n\}$ and if the nonzero entry $M^{\sigma}_{r,j}$ is colored with color $i$ then $M^{\sigma}_{r,i}$ must be a zero entry. Such a coloring will induce an oriented 4-cycle decomposition of the bipartite tournament corresponding to $M$. We achieve this by constructing an euler tour on the bipartite tournament which avoids traversing both pair of edges of any two internally disjoint $s$-$t$ 2-paths consecutively, where $s$ and $t$ belong to $V$.
Formulas for the computation of the Tutte polynomial of graphs with parallel classes Eunice Mphako-Banda; Julian A. Allagan
Electronic Journal of Graph Theory and Applications (EJGTA) Vol 6, No 1 (2018): 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.2018.6.1.8

Abstract

We give some reduction formulas for  computing the Tutte polynomial of any graph with parallel classes. Several examples are given to illustrate our results.
On central-peripheral appendage numbers of uniform central graphs Sul-Young Choi; Jonathan Needleman
Electronic Journal of Graph Theory and Applications (EJGTA) Vol 8, No 1 (2020): 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.2020.8.1.12

Abstract

In a uniform central graph (UCG) the set of eccentric vertices of a central vertex is the same for all central vertices. This collection of eccentric vertices is the centered periphery. For a pair of graphs (C,P) the central-peripheral appendage number, Aucg(C,P), is the minimum number vertices needed to be adjoined to the graphs C and P in order to construct a uniform central graph H with center V(C) and centered-periphery V(P). We compute Aucg(C,P) in terms of the radius and diameter of P and whether or not C is a complete graph. In the process we show Aucg(C, P) ≤ 6 if diam(P) > 2.   We also provide structure theorems for UCGs in terms of the centered periphery.
The (Delta,D) and (Delta,N) problems in double-step digraphs with unilateral distance Cristina Dalfo; Miquel Àngel Fiol
Electronic Journal of Graph Theory and Applications (EJGTA) Vol 2, No 1 (2014): 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.2014.2.1.1

Abstract

We study the (Delta,D) and (Delta,N) problems for double-step digraphs considering the unilateral distance, which is the minimum between the distance in the digraph and the distance in its converse digraph, obtained by changing the directions of all the arcs.The first problem consists of maximizing the number of vertices N of a digraph, given the maximum degree $\Delta$ and the unilateral diameter D*, whereas the second one (somehow dual of the first) consists of minimizing the unilateral diameter given the maximum degree and the number of vertices. We solve the first problem for every value of the unilateral diameter and the second one for infinitely many values of the number of vertices.Moreover, we compute the mean unilateral distance of the digraphs in the families considered.
On the connectivity of $k$-distance graphs Omid Khormali
Electronic Journal of Graph Theory and Applications (EJGTA) Vol 5, No 1 (2017): 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.2017.5.1.9

Abstract

For any $k \in \mathbb{N}$, the $k-$distance graph $D^{k}G$ has the same vertex set of $G$, and two vertices of $D^{k}G$ are adjacent if they are exactly distance $k$ apart in the original graph $G$. In this paper, we consider the connectivity of $D^{k}G$ and state the conditions for graph $G$ and integer $k$ such that the graph $D^{k}G$ is connected.
Minimizing the maximum sender interference by deploying additional nodes in a wireless sensor network Pushparaj Shetty D.; M. Prasanna Lakshmi
Electronic Journal of Graph Theory and Applications (EJGTA) Vol 7, No 1 (2019): 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.2019.7.1.13

Abstract

Interference is one of the major challenges faced by the communication networks. Since the interference leads to packet loss, packet collision and data re-transmission, higher the interference, higher is the energy consumption. Several algorithms were proposed for reducing the interference in a Wireless sensor network (WSN). By deploying additional nodes at an appropriate position in a WSN, it is possible to reduce the interference. We propose an algorithm in which, the main objective is to reduce the maximum Sender interference by deploying the additional nodes in the network, while connectivity of the network is preserved. We use the properties of Gabriel graph to achieve the reduction in interference. We present the simulation results which show the number of additional nodes to be deployed. The comparison of the maximum Sender interference obtained by the proposed algorithm with that of the Euclidean minimum spanning tree (MST) of the given network is presented through simulation. We show that the additional number of nodes required for deployment has an upper bound of n/2, where n is the number of nodes. We also compute the average reduction in Sender interference of the network for a various number of nodes.  
A remark on the second neighborhood problem Salman Ghazal
Electronic Journal of Graph Theory and Applications (EJGTA) Vol 3, No 2 (2015): 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.2015.3.2.6

Abstract

Seymour's second neighborhood conjecture states that every simple digraph (without digons) has a vertex whose first out-neighborhood is at most as large as its second out-neighborhood. Such a vertex is said to have the second neighborhood property (SNP). We define "good" digraphs and prove a statement that implies that every feed vertex of a tournament has the SNP. In the case of digraphs missing a matching, we exhibit a feed vertex with the SNP by refining a proof due to Fidler and Yuster and using good digraphs. Moreover, in some cases we exhibit two vertices with SNP
On maximum signless Laplacian Estrada index of graphs with given parameters II Ramin Nasiri; Hamid Reza Ellahi; Gholam Hossein Fath-Tabar; Ahmad Gholami
Electronic Journal of Graph Theory and Applications (EJGTA) Vol 6, No 1 (2018): 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.2018.6.1.14

Abstract

The signless Laplacian Estrada index of a graph G is defined as SLEE(G) = ∑ni = 1eqi where q1, q2, …, qn are the eigenvalues of the signless Laplacian matrix of G. Following the previous work in which we have identified the unique graphs with maximum signless Laplacian Estrada index with each of the given parameters, namely, number of cut edges, pendent vertices, (vertex) connectivity, and edge connectivity, in this paper we continue our characterization for two further parameters: diameter and number of cut vertices.

Page 7 of 39 | Total Record : 382

 5   6   7   8   9 

Filter by Year

2013 2025


Reset
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