Handbook of Graph Theory, 2nd Edition

Chapter 3

Directed Graphs

Section 3.1 Basic Digraph Models and Properties

Jay Yellen

Rollins College

Introduction

This section extends the basic terminology and properties begun in Chapter 1, and it describes several classical digraph models that preview later sections of the Handbook. Many of the basic methods and algorithms for digraphs closely resemble their counterparts for undirected graphs. Some general references for digraphs are [ChLeZh10], [GrYe06], and [We01]. A comprehensive and in-depth reference for digraphs is [BaGu01].

3.1.1 Terminology and Basic Facts

TERMINOLOGY NOTE: The term arc is used throughout this section instead of its synonym directed edge.

NOTATION: Often, when the digraphs under consideration do not have multi-arcs, ...