Electronic Journal of Graph Theory and Applications (EJGTA)
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
11 Documents
Search results for
, issue
"Vol 3, No 1 (2015): Electronic Journal of Graph Theory and Applications"
:
11 Documents
clear
<![CDATA[On scores, losing scores and total scores in hypertournaments ]]>
<![CDATA[Shariefuddin Pirzada]]>;
<![CDATA[Muhammad Ali Khan]]>;
<![CDATA[Zhou Guofei]]>;
<![CDATA[Koko K Kayibi]]>
<![CDATA[ Electronic Journal of Graph Theory and Applications (EJGTA) Vol 3, No 1 (2015): Electronic Journal of Graph Theory and Applications ]]>
Publisher : <![CDATA[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.1.2
<![CDATA[A $k$-hypertournament is a complete $k$-hypergraph with each $k$-edge endowed with an orientation, that is, a linear arrangement of the vertices contained in the edge. In a $k$-hypertournament, the score $s_{i}$ (losing score $r_{i}$) of a vertex $v_{i}$ is the number of arcs containing $v_{i}$ in which $v_{i}$ is not the last element (in which $v_{i}$ is the last element). The total score of $v_{i}$ is defined as $t_{i}=s_{i}-r_{i}$. In this paper we obtain stronger inequalities for the quantities $\sum_{i\in I}r_{i}$, $\sum_{i\in I}s_{i}$ and $\sum_{i\in I}t_{i}$, where $I\subseteq \{ 1,2,\ldots,n\}$. Furthermore, we discuss the case of equality for these inequalities. We also characterize total score sequences of strong $k$-hypertournaments.]]>
<![CDATA[A Study on Topological Integer Additive Set-Labeling of Graphs ]]>
<![CDATA[Sudev Naduvath]]>
<![CDATA[ Electronic Journal of Graph Theory and Applications (EJGTA) Vol 3, No 1 (2015): Electronic Journal of Graph Theory and Applications ]]>
Publisher : <![CDATA[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.1.8
<![CDATA[A set-labeling of a graph $G$ is an injective function $f:V(G)\to \mathcal{P}(X)$, where $X$ is a finite set and a set-indexer of $G$ is a set-labeling such that the induced function $f^{\oplus}:E(G)\to \mathcal{P}(X)-\{\emptyset\}$ defined by $f^{\oplus}(uv) = f(u){\oplus}f(v)$ for every $uv{\in} E(G)$ is also injective. Let $G$ be a graph and let $X$ be a non-empty set. A set-indexer $f:V(G)\to \mathcal{P}(X)$ is called a topological set-labeling of $G$ if $f(V(G))$ is a topology of $X$. An integer additive set-labeling is an injective function $f:V(G)\to \mathcal{P}(\mathbb{N}_0)$, whose associated function $f^+:E(G)\to \mathcal{P}(\mathbb{N}_0)$ is defined by $f(uv)=f(u)+f(v), uv\in E(G)$, where $\mathbb{N}_0$ is the set of all non-negative integers and $\mathcal{P}(\mathbb{N}_0)$ is its power set. An integer additive set-indexer is an integer additive set-labeling such that the induced function $f^+:E(G) \to \mathcal{P}(\mathbb{N}_0)$ defined by $f^+ (uv) = f(u)+ f(v)$ is also injective. In this paper, we extend the concepts of topological set-labeling of graphs to topological integer additive set-labeling of graphs.]]>
<![CDATA[A new characterization of trivially perfect graphs ]]>
<![CDATA[Christian Rubio Montiel]]>
<![CDATA[ Electronic Journal of Graph Theory and Applications (EJGTA) Vol 3, No 1 (2015): Electronic Journal of Graph Theory and Applications ]]>
Publisher : <![CDATA[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.1.3
<![CDATA[A graph $G$ is \emph{trivially perfect} if for every induced subgraph the cardinality of the largest set of pairwise nonadjacent vertices (the stability number) $\alpha(G)$ equals the number of (maximal) cliques $m(G)$. We characterize the trivially perfect graphs in terms of vertex-coloring and we extend some definitions to infinite graphs.]]>
<![CDATA[The signed Roman domatic number of a digraph ]]>
<![CDATA[Seyed Mahmoud Sheikholeslami]]>;
<![CDATA[Lutz Volkmann]]>
<![CDATA[ Electronic Journal of Graph Theory and Applications (EJGTA) Vol 3, No 1 (2015): Electronic Journal of Graph Theory and Applications ]]>
Publisher : <![CDATA[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.1.9
<![CDATA[Let $D$ be a finite and simple digraph with vertex set $V(D)$.A {\em signed Roman dominating function} on the digraph $D$ isa function $f:V (D)\longrightarrow \{-1, 1, 2\}$ such that$\sum_{u\in N^-[v]}f(u)\ge 1$ for every $v\in V(D)$, where $N^-[v]$ consists of $v$ andall inner neighbors of $v$, and every vertex $u\in V(D)$ for which $f(u)=-1$ has an innerneighbor $v$ for which $f(v)=2$. A set $\{f_1,f_2,\ldots,f_d\}$ of distinct signedRoman dominating functions on $D$ with the property that $\sum_{i=1}^df_i(v)\le 1$ for each$v\in V(D)$, is called a {\em signed Roman dominating family} (of functions) on $D$. The maximumnumber of functions in a signed Roman dominating family on $D$ is the {\em signed Roman domaticnumber} of $D$, denoted by $d_{sR}(D)$. In this paper we initiate the study of signed Romandomatic number in digraphs and we present some sharp bounds for $d_{sR}(D)$. In addition, wedetermine the signed Roman domatic number of some digraphs. Some of our results are extensionsof well-known properties of the signed Roman domatic number of graphs.]]>
<![CDATA[Polynomial reconstruction of the matching polynomial ]]>
<![CDATA[Xueliang Li]]>;
<![CDATA[Yongtang Shi]]>;
<![CDATA[Martin Trinks]]>
<![CDATA[ Electronic Journal of Graph Theory and Applications (EJGTA) Vol 3, No 1 (2015): Electronic Journal of Graph Theory and Applications ]]>
Publisher : <![CDATA[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.1.4
<![CDATA[The matching polynomial of a graph is the generating function of the numbers of its matchings with respect to their cardinality. A graph polynomial is polynomial reconstructible, if its value for a graph can be determined from its values for the vertex-deleted subgraphs of the same graph. This note discusses the polynomial reconstructibility of the matching polynomial. We collect previous results, prove it for graphs with pendant edges and disprove it for some graphs.]]>
<![CDATA[On energy, Laplacian energy and $p$-fold graphs ]]>
<![CDATA[Hilal A Ganie]]>;
<![CDATA[Shariefuddin Pirzada]]>;
<![CDATA[Edy Tri Baskoro]]>
<![CDATA[ Electronic Journal of Graph Theory and Applications (EJGTA) Vol 3, No 1 (2015): Electronic Journal of Graph Theory and Applications ]]>
Publisher : <![CDATA[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.1.10
<![CDATA[For a graph $G$ having adjacency spectrum ($A$-spectrum) $\lambda_n\leq\lambda_{n-1}\leq\cdots\leq\lambda_1$ and Laplacian spectrum ($L$-spectrum) $0=\mu_n\leq\mu_{n-1}\leq\cdots\leq\mu_1$, the energy is defined as $ E(G)=\sum_{i=1}^{n}|\lambda_i|$ and the Laplacian energy is defined as $LE(G)=\sum_{i=1}^{n}|\mu_i-\frac{2m}{n}|$. In this paper, we give upper and lower bounds for the energy of $KK_n^j,~1\leq j \leq n$ and as a consequence we generalize a result of Stevanovic et al. [More on the relation between Energy and Laplacian energy of graphs, MATCH Commun. Math. Comput. Chem. {\bf 61} (2009) 395-401]. We also consider strong double graph and strong $p$-fold graph to construct some new families of graphs $G$ for which $E(G)> LE(G)$.]]>
<![CDATA[Ideal basis in constructions defined by directed graphs ]]>
<![CDATA[Jemal Abawajy]]>;
<![CDATA[Andrei Kelarev]]>;
<![CDATA[Joe Ryan]]>
<![CDATA[ Electronic Journal of Graph Theory and Applications (EJGTA) Vol 3, No 1 (2015): Electronic Journal of Graph Theory and Applications ]]>
Publisher : <![CDATA[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.1.5
<![CDATA[The present article continues the investigation of visible ideal bases in constructions defined using directed graphs. This notion is motivated by its applications for the design of classication systems. Our main theorem establishes that, for every balanced digraph and each idempotent semiring with identity element, the incidence semiring of the digraph has a convenient visible ideal basis. It also shows that the elements of the basis can always be used to generate ideals with the largest possible weight among the weights of all ideals in the incidence semiring.]]>
<![CDATA[Errata: New measures of graph irregularity ]]>
<![CDATA[Clive Elphick]]>;
<![CDATA[Pawel Wocjan]]>
<![CDATA[ Electronic Journal of Graph Theory and Applications (EJGTA) Vol 3, No 1 (2015): Electronic Journal of Graph Theory and Applications ]]>
Publisher : <![CDATA[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.1.11
<![CDATA[This paper gives an errata to the paper "New measure of graph irregularity", Electronic Journal of Graph Theory and Applications {\bf 2}(1) (2014), 52-65.]]>
<![CDATA[Graphs obtained from collections of blocks ]]>
<![CDATA[Colton Magnant]]>;
<![CDATA[Pouria Salehi Nowbandegani]]>;
<![CDATA[Hua Wang]]>
<![CDATA[ Electronic Journal of Graph Theory and Applications (EJGTA) Vol 3, No 1 (2015): Electronic Journal of Graph Theory and Applications ]]>
Publisher : <![CDATA[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.1.6
<![CDATA[Given a collection of $d$-dimensional rectangular solids called blocks, no two of which sharing interior points, construct a block graph by adding a vertex for each block and an edge if the faces of the two corresponding blocks intersect nontrivially. It is known that if $d \geq 3$, such block graphs can have arbitrarily large chromatic number. We prove that the chromatic number can be bounded with only a mild restriction on the sizes of the blocks. We also show that block graphs of block configurations arising from partitions of $d$-dimensional hypercubes into sub-hypercubes are at least $d$-connected. Bounds on the diameter and the hamiltonicity of such block graphs are also discussed.]]>
<![CDATA[Subdigraphs of almost Moore digraphs induced by fixpoints of an automorphism ]]>
<![CDATA[Anita Abildgaard Sillasen]]>
<![CDATA[ Electronic Journal of Graph Theory and Applications (EJGTA) Vol 3, No 1 (2015): Electronic Journal of Graph Theory and Applications ]]>
Publisher : <![CDATA[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.1.1
<![CDATA[The degree/diameter problem for directed graphs is the problem of determining the largest possible order for a digraph with given maximum out-degree d and diameter k. An upper bound is given by the Moore bound M(d,k)=1+d+d^2+...+d^k$ and almost Moore digraphs are digraphs with maximum out-degree d, diameter k and order M(d,k)-1. In this paper we will look at the structure of subdigraphs of almost Moore digraphs, which are induced by the vertices fixed by some automorphism varphi. If the automorphism fixes at least three vertices, we prove that the induced subdigraph is either an almost Moore digraph or a diregular k-geodetic digraph of degree d'<d-1, order M(d',k)+1 and diameter k+1. As it is known that almost Moore digraphs have an automorphism r, these results can help us determine structural properties of almost Moore digraphs, such as how many vertices of each order there are with respect to r. We determine this for d=4 and d=5, where we prove that except in some special cases, all vertices will have the same order.]]>
