A Complete Characterisation of Vertex-multiplications of Trees with Diameter 5

For a connected graph $G$, let $\mathscr{D}(G)$ be the family of strong orientations of $G$; and for any $D\in\mathscr{D}(G)$, we denote by $d(D)$ the diameter of $D$. The $\textit{orientation number}$ of $G$ is defined as $\bar{d}(G)=\min\{d(D)\mid D\in \mathscr{D}(G)\}$. In 2000, Koh and Tay intro...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Willie Wong, Eng Guan Tay
Formato:	article
Lenguaje:	EN
Publicado:	Georgia Southern University 2021
Materias:	optimal orientation orientation number vertex-multiplication tree Mathematics QA1-939
Acceso en línea:	https://doaj.org/article/307efe2ef1ed4e5b836a523f0dc7a636
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:307efe2ef1ed4e5b836a523f0dc7a636
record_format	dspace
spelling	oai:doaj.org-article:307efe2ef1ed4e5b836a523f0dc7a6362021-11-16T16:59:17ZA Complete Characterisation of Vertex-multiplications of Trees with Diameter 52470-985910.20429/tag.2021.080206https://doaj.org/article/307efe2ef1ed4e5b836a523f0dc7a6362021-11-01T00:00:00Zhttps://digitalcommons.georgiasouthern.edu/tag/vol8/iss2/6https://doaj.org/toc/2470-9859For a connected graph $G$, let $\mathscr{D}(G)$ be the family of strong orientations of $G$; and for any $D\in\mathscr{D}(G)$, we denote by $d(D)$ the diameter of $D$. The $\textit{orientation number}$ of $G$ is defined as $\bar{d}(G)=\min\{d(D)\mid D\in \mathscr{D}(G)\}$. In 2000, Koh and Tay introduced a new family of graphs, $G$ vertex-multiplications, and extended the results on the orientation number of complete $n$-partite graphs. Suppose $G$ has the vertex set $V(G)=\{v_1,v_2,\ldots, v_n\}$. For any sequence of $n$ positive integers $(s_i)$, a $G$ \textit{vertex-multiplication}, denoted by $G(s_1, s_2,\ldots, s_n)$, is the graph with vertex set $V^=\bigcup_{i=1}^n{V_i}$ and edge set $E^$, where $V_i$'s are pairwise disjoint sets with $\|V_i\|=s_i$, for $i=1,2,\ldots,n$; and for any $u,v\in V^$, $uv\in E^$ if and only if $u\in V_i$ and $v\in V_j$ for some $i,j\in \{1,2,\ldots, n\}$ with $i\neq j$ such that $v_i v_j\in E(G)$. They proved a fundamental classification of $G$ vertex-multiplications, with $s_i\ge 2$ for all $i=1,2,\ldots, n$, into three classes $\mathscr{C}_0, \mathscr{C}_1$ and $\mathscr{C}_2$, and any vertex-multiplication of a tree with diameter at least 3 does not belong to the class $\mathscr{C}_2$. Furthermore, some necessary and sufficient conditions for $\mathscr{C}_0$ were established for vertex-multiplications of trees with diameter $5$. In this paper, we give a complete characterisation of vertex-multiplications of trees with diameter $5$ in $\mathscr{C}_0$ and $\mathscr{C}_1$.Willie WongEng Guan TayGeorgia Southern Universityarticleoptimal orientationorientation numbervertex-multiplicationtreeMathematicsQA1-939ENTheory and Applications of Graphs, Vol 8, Iss 2 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	optimal orientation orientation number vertex-multiplication tree Mathematics QA1-939
spellingShingle	optimal orientation orientation number vertex-multiplication tree Mathematics QA1-939 Willie Wong Eng Guan Tay A Complete Characterisation of Vertex-multiplications of Trees with Diameter 5
description	For a connected graph $G$, let $\mathscr{D}(G)$ be the family of strong orientations of $G$; and for any $D\in\mathscr{D}(G)$, we denote by $d(D)$ the diameter of $D$. The $\textit{orientation number}$ of $G$ is defined as $\bar{d}(G)=\min\{d(D)\mid D\in \mathscr{D}(G)\}$. In 2000, Koh and Tay introduced a new family of graphs, $G$ vertex-multiplications, and extended the results on the orientation number of complete $n$-partite graphs. Suppose $G$ has the vertex set $V(G)=\{v_1,v_2,\ldots, v_n\}$. For any sequence of $n$ positive integers $(s_i)$, a $G$ \textit{vertex-multiplication}, denoted by $G(s_1, s_2,\ldots, s_n)$, is the graph with vertex set $V^=\bigcup_{i=1}^n{V_i}$ and edge set $E^$, where $V_i$'s are pairwise disjoint sets with $\|V_i\|=s_i$, for $i=1,2,\ldots,n$; and for any $u,v\in V^$, $uv\in E^$ if and only if $u\in V_i$ and $v\in V_j$ for some $i,j\in \{1,2,\ldots, n\}$ with $i\neq j$ such that $v_i v_j\in E(G)$. They proved a fundamental classification of $G$ vertex-multiplications, with $s_i\ge 2$ for all $i=1,2,\ldots, n$, into three classes $\mathscr{C}_0, \mathscr{C}_1$ and $\mathscr{C}_2$, and any vertex-multiplication of a tree with diameter at least 3 does not belong to the class $\mathscr{C}_2$. Furthermore, some necessary and sufficient conditions for $\mathscr{C}_0$ were established for vertex-multiplications of trees with diameter $5$. In this paper, we give a complete characterisation of vertex-multiplications of trees with diameter $5$ in $\mathscr{C}_0$ and $\mathscr{C}_1$.
format	article
author	Willie Wong Eng Guan Tay
author_facet	Willie Wong Eng Guan Tay
author_sort	Willie Wong
title	A Complete Characterisation of Vertex-multiplications of Trees with Diameter 5
title_short	A Complete Characterisation of Vertex-multiplications of Trees with Diameter 5
title_full	A Complete Characterisation of Vertex-multiplications of Trees with Diameter 5
title_fullStr	A Complete Characterisation of Vertex-multiplications of Trees with Diameter 5
title_full_unstemmed	A Complete Characterisation of Vertex-multiplications of Trees with Diameter 5
title_sort	complete characterisation of vertex-multiplications of trees with diameter 5
publisher	Georgia Southern University
publishDate	2021
url	https://doaj.org/article/307efe2ef1ed4e5b836a523f0dc7a636
work_keys_str_mv	AT williewong acompletecharacterisationofvertexmultiplicationsoftreeswithdiameter5 AT engguantay acompletecharacterisationofvertexmultiplicationsoftreeswithdiameter5 AT williewong completecharacterisationofvertexmultiplicationsoftreeswithdiameter5 AT engguantay completecharacterisationofvertexmultiplicationsoftreeswithdiameter5
_version_	1718426291814793216

A Complete Characterisation of Vertex-multiplications of Trees with Diameter 5

Ejemplares similares