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 10 Documents
 1 
Search results for , issue "Vol 3, No 2 (2015): Electronic Journal of Graph Theory and Applications" : 10 Documents clear
On a directed tree problem motivated by a newly introduced graph product Antoon H. Boode; Hajo Broersma; Jan F. Broenink
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.5

Abstract

In this paper we introduce and study a directed tree problem motivated by a new graph product that we have recently introduced and analysed in two conference contributions in the context of periodic real-time processes. While the two conference papers were focussing more on the applications, here we mainly deal with the graph theoretical and computational complexity issues. We show that the directed tree problem is NP-complete and present and compare several heuristics for this problem.
Log-concavity of the genus polynomials of Ringel Ladders Jonathan L Gross; Toufik Mansour; Thomas W. Tucker; David G.L. Wang
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.1

Abstract

A Ringel ladder can be formed by a self-bar-amalgamation operation on a symmetric ladder, that is, by joining the root vertices on its end-rungs. The present authors have previously derived criteria under which linear chains of copies of one or more graphs have log-concave genus polyno- mials. Herein we establish Ringel ladders as the first significant non-linear infinite family of graphs known to have log-concave genus polynomials. We construct an algebraic representation of self-bar-amalgamation as a matrix operation, to be applied to a vector representation of the partitioned genus distribution of a symmetric ladder. Analysis of the resulting genus polynomial involves the use of Chebyshev polynomials. This paper continues our quest to affirm the quarter-century-old conjecture that all graphs have log-concave genus polynomials.
The complete list of Ramsey $(2K_2,K_4)$-minimal graphs Kristiana Wijaya; Edy Tri Baskoro; Hilda Assiyatun; Djoko Suprijanto
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.9

Abstract

Let $F, G,$ and $H$ be non-empty graphs. The notation $F \rightarrow (G,H)$ means that if all edges of $F$ are arbitrarily colored by red or blue, then either the subgraph of $F$ induced by all red edges contains a graph $G$ or the subgraph of $F$ induced by all blue edges contains a graph $H.$ A graph $F$ satisfying two conditions: $F \rightarrow (G,H)$ and $(F-e) \nrightarrow (G,H)$ for every $e \in E(F)$ is called a Ramsey $(G,H)-$minimal graph. In this paper, we determine all non-isomorphic Ramsey $(2K_2,K_4)$-minimal 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$.
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 the independent set interdiction problem Gholam Hassan Shirdel; Nasrin Kahkeshani
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.2

Abstract

The purpose of the independent set interdiction problem in the weighted graph $G$ is to determine a set of vertices $R^*$ such that the weight of the maximum independent set in $G-R^*$ is minimized. We define an approximate solution for this problem. Then, an upper bound for the relative error of this problem is obtained. We show that the limit of the relative error of the independent set interdiction problem in some subclasses of the generalized Petersen graphs is zero as the number of vertices tends to infinity.
Reciprocal complementary distance spectra and reciprocal complementary distance energy of line graphs of regular graphs Harishchandra S. Ramane; Ashwini S. Yalnaik
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.10

Abstract

The reciprocal complementary distance (RCD) matrix of a graph $G$ is defined as $RCD(G) = [rc_{ij}]$ where $rc_{ij} = \frac{1}{1+D-d_{ij}}$ if $i \neq j$ and $rc_{ij} = 0$, otherwise, where $D$ is the diameter of $G$ and $d_{ij}$ is the distance between the vertices $v_i$ and $v_j$ in $G$. The $RCD$-energy of $G$ is defined as the sum of the absolute values of the eigenvalues of $RCD(G)$. Two graphs are said to be $RCD$-equienergetic if they have same $RCD$-energy. In this paper we show that the line graph of certain regular graphs has exactly one positive $RCD$-eigenvalue. Further we show that $RCD$-energy of line graph of these regular graphs is solely depends on the order and regularity of $G$. This results enables to construct pairs of $RCD$-equienergetic graphs of same order and having different $RCD$-eigenvalues.
On middle cube graphs C. Dalfo; M. A. Fiol; M. Mitjana
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.3

Abstract

We study a family of graphs related to the $n$-cube. The middle cube graph of parameter k is the subgraph of $Q_{2k-1}$ induced by the set of vertices whose binary representation has either $k-1$ or $k$ number of ones. The middle cube graphs can be obtained from the well-known odd graphs by doubling their vertex set. Here we study some of the properties of the middle cube graphs in the light of the theory of distance-regular graphs. In particular, we completely determine their spectra (eigenvalues and their multiplicities, and associated eigenvectors).
Odd sum labeling of graphs obtained by duplicating any edge of some graphs S. Arockiaraj; P. Mahalakshmi; P. Namasivayam
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.8

Abstract

An injective function $f:V(G)\rightarrow \{0,1,2,\dots,q\}$ is an odd sum labeling if the induced edge labeling $f^*$ defined by $f^*(uv)=f(u)+f(v),$ for all $uv\in E(G),$ is bijective and $f^*(E(G))=\{1,3,5,\dots,2q-1\}.$ A graph is said to be an odd sum graph if it admits an odd sum labeling. In this paper we study the odd sum property of graphs obtained by duplicating any edge of some graphs.
Degree Associated Edge Reconstruction Number of Graphs with Regular Pruned Graph P. Anusha Devi; S. Monikandan
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.4

Abstract

An ecard of a graph $G$ is a subgraph formed by deleting an edge. A da-ecard specifies the degree of the deleted edge along with the ecard. The degree associated edge reconstruction number of a graph $G,~dern(G),$ is the minimum number of da-ecards that uniquely determines $G.$  The adversary degree associated edge reconstruction number of a graph $G, adern(G),$ is the minimum number $k$ such that every collection of $k$ da-ecards of $G$ uniquely determines $G.$ The maximal subgraph without end vertices of a graph $G$ which is not a tree is the pruned graph of $G.$ It is shown that $dern$ of complete multipartite graphs and some connected graphs with regular pruned graph is $1$ or $2.$ We also determine $dern$ and $adern$ of corona product of standard graphs.

Page 1 of 1 | Total Record : 10

 1 

Filter by Year

2015 2015


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