NDLI: Asteroidal Triple-Free Graphs

Please wait, while we are loading the content...

Asteroidal Triple-Free Graphs

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Olariu, Stephan Stewart, Lorna Corneil, Derek G.
Copyright Year	1997
Abstract	An independent set of three vertices such that each pair is joined by a path that avoids the neighborhood of the third is called an asteroidal triple. A graph is asteroidal triple-free (AT-free) if it contains no asteroidal triples. The motivation for this investigation was provided, in part, by the fact that the AT-free graphs provide a common generalization of interval, permutation, trapezoid, and cocomparability graphs. The main contribution of this work is to investigate and reveal fundamental structural properties of AT-free graphs. Specifically, we show that every connected AT-free graph contains a dominating pair, that is, a pair of vertices such that every path joining them is a dominating set in the graph. We then provide characterizations of AT-free graphs in terms of dominating pairs and minimal triangulations. Subsequently, we state and prove a decomposition theorem for AT-free graphs. An assortment of other properties of AT-free graphs is also provided. These properties generalize known structural properties of interval, permutation, trapezoid, and cocomparability graphs.
Starting Page	399
Ending Page	430
Page Count	32
File Format	PDF
ISSN	08954801
DOI	10.1137/S0895480193250125
e-ISSN	10957146
Journal	SIAM Journal on Discrete Mathematics (SJDMEC)
Issue Number	3
Volume Number	10
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2006-08-01
Access Restriction	Subscribed
Subject Keyword	trapezoid graphs cocomparability graphs graph decompositions dominating pairs Structural characterization of families of graphs Graph theory structural graph theory asteroidal triple-free graphs interval graphs asteroidal triples permutation graphs
Content Type	Text
Resource Type	Article
Subject	Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Dominating Pair Graphs

Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs

Approximating the bandwidth for asteroidal triple-free graphs.

Asteroidal triple-free graphs (1997).

Asteroidal triple-free graphs (1997)

Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs (1997)

Boxicity and cubicity of asteroidal triple free graphs (2009).

Powers of Asteroidal Triple-free Graphs with Applications

Powers of asteroidal triple-free graphs with applications?.

Asteroidal Triple-Free Graphs

Similar Documents

Dominating Pair Graphs

Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs

Approximating the bandwidth for asteroidal triple-free graphs.

Asteroidal triple-free graphs (1997).

Asteroidal triple-free graphs (1997)

Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs (1997)

Boxicity and cubicity of asteroidal triple free graphs (2009).

Powers of Asteroidal Triple-free Graphs with Applications

Powers of asteroidal triple-free graphs with applications?.

Asteroidal Triple-Free Graphs