On oriented diameter of (n,k)-star graphs

Assignment of one of two possible directions to every edge of an undirected graph G=(V,E) is called an orientation of G. The resulting directed graph is denoted by G⃗. A strong orientation is one in which every vertex is reachable from every other vertex via a directed path in G⃗. The diameter of G⃗...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2024-09, Vol.354, p.214-228
Main Authors: Ajish Kumar, K.S., Sasidharan, Birenjith, Sudeep, K.S.
Format: Article
Language:English
Subjects:
[formula omitted]-star graphs
Oriented diameter
Strong orientation
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Assignment of one of two possible directions to every edge of an undirected graph G=(V,E) is called an orientation of G. The resulting directed graph is denoted by G⃗. A strong orientation is one in which every vertex is reachable from every other vertex via a directed path in G⃗. The diameter of G⃗, i.e., the maximum distance from any vertex to any other vertex, depends on the particular orientation. The minimum diameter among all possible orientations of G is called the oriented diameterdiam⃗(G) of G. Let n,k be two integers such that 1≤kn2, n3
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2022.04.017