B1-ORIENTABLE GRAPHS

Purchase PDF

Published: 2015-11-19

Page: 265-272


BACHIR SADI *

Département de Mathématiques, LAROMAD, Faculté des Sciences, Université Mouloud Mammeri de Tizi-ouzou, Algeria.

*Author to whom correspondence should be addressed.


Abstract

The aim of this paper is to find a particular orientation U of an undirected graph G = (X, E), called B1 –orientation [1]. The directed graph G0 = (X,U) is such that: u, v, w Î X ,(u,v) ÎU and (w, v) ÎU implies that the edge [uw] ÎE. This class of B1 -orientable graphs includes triangulated graphs and arc-circular graphs, as mentioned in [2,3]. We propose here, an algorithm which gives a B1 -orientation of an undirected graph G = (X, E) if G is B1 -orientable or exits with output: G is not B1 -orientable. The complexity of this algorithm is in O(n.D2 ), where n =  X and D  is the maximum degree of G. We show too, by an algorithm, that the class of triangulated graphs is included in this new class of graphs [4,5].

Keywords: Graph orientation, B1 –orientation, B1 -orientable graphs


How to Cite

SADI, B. (2015). B1-ORIENTABLE GRAPHS. Asian Journal of Mathematics and Computer Research, 9(3), 265–272. Retrieved from https://ikprress.org/index.php/AJOMCOR/article/view/195

Downloads

Download data is not yet available.