2009-03-15, English, Article, Journal or magazine article edition: Asteroids in rooted and directed path graphs. Cameron, Kathie; Hoang, ChiNh T.; Leveque, Benjamin

User activity

Share to:
 
Bookmark: http://trove.nla.gov.au/version/204287448
Physical Description
  • Magazine/​Journal article
Published
  • Elsevier B.V., 2009 March 15
Language
  • English

Edition details

Title
  • Asteroids in rooted and directed path graphs.
Appears In
  • Electronic Notes in Discrete Mathematics, v.32, 2009 March 15, p.67(8) (ISSN: 1571-0653)
Author
  • Cameron, Kathie
  • Hoang, ChiNh T.
  • Leveque, Benjamin
Published
  • Elsevier B.V., 2009 March 15
Physical Description
  • Magazine/​Journal article
Subjects
Target Audience
  • Academic
Summary
  • To link to full-text access for this article, visit this link: http:/​/​dx.doi.org/​10.1016/​j.endm.2009.02.010 Byline: Kathie Cameron, Chinh T. Hoang, Benjamin Leveque Keywords: intersection graph; directed path graph; asteroidal triple Abstract: An asteroidal triple is a stable set of three vertices such that each pair is connected by a path avoiding the neighborhood of the third vertex. Asteroidal triples play a central role in a classical characterization of interval graphs by Lekkerkerker and Boland. Their result says that a chordal graph is an interval graph if and only if it contains no asteroidal triple. In this paper, we prove an analogous theorem for directed path graphs which are the intersection graphs of directed paths in a directed tree. For this purpose, we introduce the notion of a strong path. Two non-adjacent vertices are linked by a strong path if either they have a common neighbor or they are the endpoints of two vertex-disjoint chordless paths satisfying certain conditions. A strong asteroidal triple is an asteroidal triple such that each pair is linked by a strong path. We prove that a chordal graph is a directed path graph if and only if it contains no strong asteroidal triple. We also introduce a related notion of asteroidal quadruple, and conjecture a characterization of rooted path graphs which are the intersection graphs of directed paths in a rooted tree. Author Affiliation: Wilfrid Laurier University, Waterloo, Canada Article Note: (footnote) [star] Research supported by the Natural Sciences and Engineering Research Council of Canada (NSERC).
Terms of Use
  • COPYRIGHT 2009 Elsevier B.V.
Language
  • English
Database
  • Gale Academic OneFile
Identifier
  • 350552755

Get this edition

Via a library membership

Library View online via
Australian Bureau of Statistics. Castles Library.
Australian College of Physical Education. Australian College of Physical Education Library.
Australian Catholic University. Alumni Access.
Australian Catholic University.
Australian Institute of Professional Education.
Australian Lutheran College. Lohe Memorial Library.
Australian School of Management. Perth Campus Library.
Avondale College. Avondale College of Higher Education Sydney Campus Library.
University of Adelaide. Barr Smith Library.
Blue Mountains International Hotel Management School.
Bond University. John and Alison Kearney Library .
Campion College Australia.
Charles Darwin University. Casuarina Campus Library.
Cengage Education.
Christian Heritage College. Christian Heritage College Library.
Deakin University. Deakin University Library.
Edith Cowan University. Edith Cowan University Library.
Australian College of Natural Medicine Pty Ltd. Endeavour College of Natural Health Library.
Excelsia College. Excelsia College Library.
Kaplan Professional. Library.
Fire & Rescue NSW. FRNSW Library.
University of Notre Dame Australia. Galvin Medical Library.
Holmesglen Institute of TAFE. Holmesglen Learning Commons.
International College of Management, Sydney. ICMS Library.
Macquarie University. Macquarie University Library.
Marcus Oldham College. Sir James Darling Resource Centre.
Melbourne Library Service.
Monash University. Monash University Library.
Moore Theological College. Moore Theological College Library.
SA Mental Health Services.
Sydney Missionary and Bible College. J.T.H. Kerr Library.
South Australian Research and Development Institute. South Australian Aquatic Sciences Centre Library.
South Western Sydney Institute of TAFE.
Swinburne University of Technology. Swinburne Library.
Tabor College Victoria.
Tabor Adelaide. Tabor College Library.
The Southport School. Senior Library.
Think: Education Group. Think Education Group Learning Resource Centre.
University of New England. Dixson Library.
University of Canberra. University of Canberra Library.
University of Wollongong. University of Wollongong Library.
University of Queensland. University of Queensland Library. UQ Library Cyberschool.
Catholic Institute of Sydney. Veech Library.
Western Sydney University. Hawkesbury Campus Library.
Show 0 more libraries...
Library View online via
Australian Bureau of Statistics. Castles Library.
University of Canberra. University of Canberra Library.
Show 0 more libraries...
Library View online via
Australian College of Physical Education. Australian College of Physical Education Library.
Australian Catholic University. Alumni Access.
Australian Catholic University.
Australian Institute of Professional Education.
Avondale College. Avondale College of Higher Education Sydney Campus Library.
Blue Mountains International Hotel Management School.
Campion College Australia.
Cengage Education.
Excelsia College. Excelsia College Library.
Kaplan Professional. Library.
Fire & Rescue NSW. FRNSW Library.
International College of Management, Sydney. ICMS Library.
Macquarie University. Macquarie University Library.
Moore Theological College. Moore Theological College Library.
Sydney Missionary and Bible College. J.T.H. Kerr Library.
South Western Sydney Institute of TAFE.
Think: Education Group. Think Education Group Learning Resource Centre.
University of New England. Dixson Library.
University of Wollongong. University of Wollongong Library.
Catholic Institute of Sydney. Veech Library.
Western Sydney University. Hawkesbury Campus Library.
Show 0 more libraries...
Library View online via
Charles Darwin University. Casuarina Campus Library.
Show 0 more libraries...
Library View online via
Bond University. John and Alison Kearney Library .
Christian Heritage College. Christian Heritage College Library.
Australian College of Natural Medicine Pty Ltd. Endeavour College of Natural Health Library.
The Southport School. Senior Library.
University of Queensland. University of Queensland Library. UQ Library Cyberschool.
Show 0 more libraries...
Library View online via
Australian Lutheran College. Lohe Memorial Library.
University of Adelaide. Barr Smith Library.
SA Mental Health Services.
South Australian Research and Development Institute. South Australian Aquatic Sciences Centre Library.
Tabor Adelaide. Tabor College Library.
Show 0 more libraries...
Library View online via
Deakin University. Deakin University Library.
Holmesglen Institute of TAFE. Holmesglen Learning Commons.
Marcus Oldham College. Sir James Darling Resource Centre.
Melbourne Library Service.
Monash University. Monash University Library.
Swinburne University of Technology. Swinburne Library.
Tabor College Victoria.
Show 0 more libraries...

With access conditions

Published in

Some editions of the publication "Electronic notes in discrete mathematics" are available from these libraries. The edition containing this article ( v.32, 2009 March 15, p.67(8) ) may not be available:

  • Set up My libraries

    How do I set up "My libraries"?

    In order to set up a list of libraries that you have access to, you must first login or sign up. Then set up a personal list of libraries from your profile page by clicking on your user name at the top right of any screen.

  • All (5)
  • NSW (2)
  • QLD (2)
  • WA (1)
None of your libraries hold this item.

These 5 locations in All:

Library Access Call number(s) Formats held Language
Charles Sturt University. CSU Library - Electronic Resources (shared). Open to the public 001668122; Full Text Available; Elsevier SD Freedom Collection - Available from 1999 volume: 1 Conference Proceedings English
Edith Cowan University. Edith Cowan University Library. Open to the public Conference Proceedings English
Griffith University. Griffith University Library. Open to the public .b15813940; Electronic Resource : Publ. may restrict Doc. Del. Conference Proceedings English
Southern Cross University. University Library Lismore. Open to the public Electronic resource - Check catalogue for holdings Conference Proceedings English
University of Queensland. University of Queensland Library. Open to the public .b2256729x; Online access via ScienceDirect : v.1- (1999)-. Available for document delivery - restrictions apply Conference Proceedings English
Show 0 more libraries...
None of your libraries hold this item.

These 2 locations in New South Wales:

Library Access Call number(s) Formats held Language
Charles Sturt University. CSU Library - Electronic Resources (shared). Open to the public 001668122; Full Text Available; Elsevier SD Freedom Collection - Available from 1999 volume: 1 Conference Proceedings English
Southern Cross University. University Library Lismore. Open to the public Electronic resource - Check catalogue for holdings Conference Proceedings English
Show 0 more libraries...
None of your libraries hold this item.

These 2 locations in Queensland:

Library Access Call number(s) Formats held Language
Griffith University. Griffith University Library. Open to the public .b15813940; Electronic Resource : Publ. may restrict Doc. Del. Conference Proceedings English
University of Queensland. University of Queensland Library. Open to the public .b2256729x; Online access via ScienceDirect : v.1- (1999)-. Available for document delivery - restrictions apply Conference Proceedings English
Show 0 more libraries...
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.

User activity


e.g. test cricket, Perth (WA), "Parkes, Henry"

Separate different tags with a comma. To include a comma in your tag, surround the tag with double quotes.

Be the first to add a tag for this edition

Be the first to add this to a list

Comments and reviews

What are comments? Add a comment

No user comments or reviews for this version

Add a comment