On the number of connected convex subgraphs of a connected acyclic digraph

Gregory Gutin; Anders Yeo

doi:10.1016/j.dam.2008.07.010

On the number of connected convex subgraphs of a connected acyclic digraph

Gregory Gutin, Anders Yeo

Royal Holloway University of London

Research output: Contribution to journal › Article › peer-review

9 Citations (Scopus)

Abstract

A digraph D is connected if the underlying undirected graph of D is connected. A subgraph H of an acyclic digraph D is convex if there is no directed path between vertices of H which contains an arc not in H. We find the minimum and maximum possible number of connected convex subgraphs in a connected acyclic digraph of order n. Connected convex subgraphs of connected acyclic digraphs are of interest in the area of modern embedded processors technology.

Original language	English
Pages (from-to)	1660-1662
Number of pages	3
Journal	Discrete Applied Mathematics
Volume	157
Issue number	7
DOIs	https://doi.org/10.1016/j.dam.2008.07.010
Publication status	Published - 6 Apr 2009
Externally published	Yes

Keywords

Acyclic digraphs
Connected subgraphs
Convex subgraphs
Enumeration

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.dam.2008.07.010

Cite this

@article{827053eb255949eb9bd7620aaf012159,

title = "On the number of connected convex subgraphs of a connected acyclic digraph",

abstract = "A digraph D is connected if the underlying undirected graph of D is connected. A subgraph H of an acyclic digraph D is convex if there is no directed path between vertices of H which contains an arc not in H. We find the minimum and maximum possible number of connected convex subgraphs in a connected acyclic digraph of order n. Connected convex subgraphs of connected acyclic digraphs are of interest in the area of modern embedded processors technology.",

keywords = "Acyclic digraphs, Connected subgraphs, Convex subgraphs, Enumeration",

author = "Gregory Gutin and Anders Yeo",

year = "2009",

month = apr,

day = "6",

doi = "10.1016/j.dam.2008.07.010",

language = "English",

volume = "157",

pages = "1660--1662",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "7",

}

TY - JOUR

T1 - On the number of connected convex subgraphs of a connected acyclic digraph

AU - Gutin, Gregory

AU - Yeo, Anders

PY - 2009/4/6

Y1 - 2009/4/6

N2 - A digraph D is connected if the underlying undirected graph of D is connected. A subgraph H of an acyclic digraph D is convex if there is no directed path between vertices of H which contains an arc not in H. We find the minimum and maximum possible number of connected convex subgraphs in a connected acyclic digraph of order n. Connected convex subgraphs of connected acyclic digraphs are of interest in the area of modern embedded processors technology.

AB - A digraph D is connected if the underlying undirected graph of D is connected. A subgraph H of an acyclic digraph D is convex if there is no directed path between vertices of H which contains an arc not in H. We find the minimum and maximum possible number of connected convex subgraphs in a connected acyclic digraph of order n. Connected convex subgraphs of connected acyclic digraphs are of interest in the area of modern embedded processors technology.

KW - Acyclic digraphs

KW - Connected subgraphs

KW - Convex subgraphs

KW - Enumeration

UR - https://www.scopus.com/pages/publications/61849102285

U2 - 10.1016/j.dam.2008.07.010

DO - 10.1016/j.dam.2008.07.010

M3 - Article

AN - SCOPUS:61849102285

SN - 0166-218X

VL - 157

SP - 1660

EP - 1662

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 7

ER -

On the number of connected convex subgraphs of a connected acyclic digraph

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this