Opuscula Mathematica
Loading...
ISSN 1232-9274
e-ISSN: 2300-6919
Issue Date
2017
Volume
Vol. 37
Number
No. 4
Description
Journal Volume
Opuscula Mathematica
Vol. 37 (2017)
Projects
Pages
Articles
On Fibonacci numbers in edge coloured trees
(Wydawnictwa AGH, 2017) Bednarz, Urszula; Bród, Dorota; Szynal-Liana, Anetta; Włoch, Iwona; Wołowiec-Musiał, Małgorzata
In this paper we show the applications of the Fibonacci numbers in edge coloured trees. We determine the second smallest number of all $(A,2B)$-edge colourings in trees. We characterize the minimum tree achieving this second smallest value.
Colourings of (k-r,k)-trees
(Wydawnictwa AGH, 2017) Borowiecki, Mieczysław; Patil, H.P.
Trees are generalized to a special kind of higher dimensional complexes known as $(j,k)$-trees ([L. W. Beineke, R. E. Pippert, On the structure of $(m,n)$-trees, Proc. 8th S-E Conf. Combinatorics, Graph Theory and Computing, 1977, 75-80]), and which are a natural extension of $k$-trees for $j=k−1$. The aim of this paper is to study$(k−r,k)$-trees ([H. P. Patil, Studies on $k$-trees and some related topics, PhD Thesis, University of Warsaw, Poland, 1984]), which are a generalization of $k$-trees (or usual trees when $k=1$). We obtain the chromatic polynomial of $(k−r,k)$-trees and show that any two $(k−r,k)$-trees of the same order are chromatically equivalent. However, if $r\neq 1$ in any $(k−r,k)$-tree $G$, then it is shown that there exists another chromatically equivalent graph $H$, which is not a $(k−r,k)$-tree. Further, the vertex-partition number and generalized total colourings of $(k−r,k)$-trees are obtained. We formulate a conjecture about the chromatic index of $(k−r,k)$-trees, and verify this conjecture in a number of cases. Finally, we obtain a result of [M. Borowiecki, W. Chojnacki, Chromatic index of $k$-trees, Discuss. Math. 9 (1988), 55-58] as a corollary in which $k$-trees of Class 2 are characterized.
Spanning trees with a bounded number of leaves
(Wydawnictwa AGH, 2017) Cai, Junqing; Flandrin, Evelyne; Li, Hao; Sun, Qiang
In 1998, H. Broersma and H. Tuinstra proved that: Given a connected graph $G$ with $n\geq 3$ vertices, if $d(u)+d(v)\geq n-k+1$ for all non-adjacent vertices u and v of $G(k\geq 1)$, then $G$ has a spanning tree with at most $k$ leaves. In this paper, we generalize this result by using implicit degree sum condition of $t$($2\leq t\leq k$) independent vertices and we prove what follows: Let $G$ be a connected graph on $n\geq 3$ vertices and $k\geq 2$ be an integer. If the implicit degree sum of any $t$ independent vertices is at least $\frac{t(n-k)}{2}+1$ for ($k\geq t\geq 2$), then $G$ has a spanning tree with at most $k$ leaves.
The metric dimension of circulant graphs and their Cartesian products
(Wydawnictwa AGH, 2017) Chau, Kevin; Gosselin, Shonda
Let $G=(V,E)$ be a connected graph (or hypergraph) and let $d(x,y)$ denote the distance between vertices $x,y\in V(G)$. A subset $W\subseteq V(G)$ is called a resolving set for $G$ if for every pair of distinct vertices $x,y\in V(G)$, there is $w\in W$ such that $d(x,w)\neq d(y,w)$. The minimum cardinality of a resolving set for $G$ is called the metric dimension of $G$, denoted by $\beta(G)$. The circulant graph $C_{n}(1,2,\ldots,t)$ has vertex set $\{v_0,v_1,\ldots,v_{n−1}\}$ and edges $v_{i}v_{i+j}$ where $0\leq i\leq n−1$ and $1\leq j\leq t$ and the indices are taken modulo $n$ ($2\leq t\leq\left\lfloor\frac{n}{2}\right\rfloor$). In this paper we determine the exact metric dimension of the circulant graphs $C_n(1,2,\ldots,t)$, extending previous results due to Borchert and Gosselin (2013), Grigorious et al. (2014), and Vetrík (2016). In particular, we show that $\beta(C_n(1,2,\ldots,t))=\beta(C_{n+2t}(1,2,\ldots,t))$ for large enough $n$, which implies that the metric dimension of these circulants is completely determined by the congruence class of n modulo $2$t. We determine the exact value of $\beta(C_n(1,2,\ldots,t))$ for $n\equiv 2\bmod 2t$ and $n\equiv (t+1)\bmod 2t$ and we give better bounds on the metric dimension of these circulants for $n\equiv 0\bmod 2t$ and $n\equiv 1 \bmod 2t$. In addition, we bound the metric dimension of Cartesian products of circulant graphs.
Acyclic sum-list-colouring of grids and other classes of graphs
(Wydawnictwa AGH, 2017) Drgas-Burchardt, Ewa; Drzystek, Agata
In this paper we consider list colouring of a graph $G$ in which the sizes of lists assigned to different vertices can be different. We colour $G$ from the lists in such a way that each colour class induces an acyclic graph. The aim is to find the smallest possible sum of all the list sizes, such that, according to the rules, $G$ is colourable for any particular assignment of the lists of these sizes. This invariant is called the $D_1$-sum-choice-number of $G$. In the paper we investigate the $D_1$-sum-choice-number of graphs with small degrees. Especially, we give the exact value of the $D_1$-sum-choice-number for each grid $P_n\square P_m$, when at least one of the numbers $n$, $m$ is less than five, and for each generalized Petersen graph. Moreover, we present some results that estimate the $D_1$-sum-choice-number of an arbitrary graph in terms of the decycling number, other graph invariants and special subgraphs.