NPS logo Naval Postgraduate School
Dudley Knox Library
        View Item 
        •   Calhoun Home
        • Faculty and Researchers
        • Faculty and Researchers Collection
        • View Item
        •   Calhoun Home
        • Faculty and Researchers
        • Faculty and Researchers Collection
        • View Item
        • How to search in Calhoun
        • My Accounts
        • Ask a Librarian
        JavaScript is disabled for your browser. Some features of this site may not work without it.

        Browse

        All of CalhounCollectionsThis Collection

        My Account

        LoginRegister

        Statistics

        Most Popular ItemsStatistics by CountryMost Popular Authors

        On the hardness of recognizing triangular line graphs

        Thumbnail
        View/Open
        Icon10071178.pdf (606.3Kb)
        Download Record
        Download to EndNote/RefMan (RIS)
        Download to BibTex
        Author
        Anand, Pranav
        Escuadro, Henry
        Gera, Ralucca
        Hartke, Stephen G.
        Stolee, Derrick
        Date
        2010
        Metadata
        Show full item record
        Abstract
        Given a graph G, its triangular line graph is the graph T(G) with vertex set consisting of the edges of G and adjacencies between edges that are incident in G as well as being within a common triangle. Graphs with a representation as the triangular line graph of some graph G are triangular line graphs, which have been studied under many names including anti-Gallai graphs, 2-in-3 graphs, and link graphs. While closely related to line graphs, triangular line graphs have been difficult to understand and characterize. Van Bang Le asked if recognizing triangular line graphs has an efficient algorithm or is computationally complex. We answer this question by proving that the complexity of recognizing triangular line graphs is NP-complete via a reduction from 3-SAT.
        Description
        Discrete Math Volume 312, Issue 17 (2012)||The article of record as published may be located at http://dx.doi.org/10.1016/j.disc.2011.11.037
        URI
        http://hdl.handle.net/10945/35436
        Collections
        • Faculty and Researchers Collection

        Related items

        Showing items related by title, author, creator and subject.

        • Thumbnail

          Number of test samples needed to obtain a desired Bayesian confidence interval for a proportion. 

          Ipekkan, Ahmet Ziyaeddin (Monterey, California. Naval Postgraduate School, 1989);
          One recurring problem in military operational test and evaluation is determination of the number of items to test. This thesis describes a Bayesian method to determine the sample size that is needed to estimate a ...
        • Thumbnail

          A characterization of graphs with interval two-step graphs 

          Merz, Sarah K.; Rasmussen, Craig W.; Lundgren, J. Richard; Maybee, John Stanley (Monterey, California. Naval Postgraduate School, 1993); NPS-MA-93-021
          One of the intriguing open problems on competition graphs is determining what digraphs have interval competition graphs. In this paper we consider this problem for the class of loopless symmetric digraphs. Here we first ...
        • Thumbnail

          A Characterization of Graphs With Interval Two-Step Graphs 

          Lundgren, J. Richard; Merz, Sarah K.; Maybee, John S.; Rasmussen, Craig W. (Norrth-Holland, 1995);
          One of the intriguing open problems on competition graphs is determining what digraphs have interval competition graphs. This problem originated in the work of Cohen on food webs. We consider it for the class of loopless ...
        Feedback

        411 Dyer Rd. Bldg. 339
        Monterey, CA 93943

         

        circdesk@nps.edu
        (831) 656-2947
        DSN 756-2947

        Start Your Research

        • Research Guides
        • How to Cite
        • Search Basics
        • Ask a Librarian
        • Library Liaisons
        • Graduate Writing Center
        • Thesis Processing Office
        • Statistics, Maps & More
        • Copyright at NPS

        Find & Download

        • Databases List
        • Articles, Books & More
        • NPS Theses
        • NPS Faculty Publications: Calhoun
        • Journal Titles
        • Course Reserves

        Use the Library

        • My Accounts
        • Request Article or Book
        • Borrow, Renew, Return
        • Remote Access
        • Workshops & Tours
        • For Faculty & Researchers
        • For International Students
        • For Alumni
        • Print, Copy, Scan, Fax
        • Rooms & Study Spaces
        • Floor Map
        • Computers & Software
        • Adapters, Lockers & More

        Collections

        • NPS Archive: Calhoun
        • Restricted Resources
        • Special Collections & Archives
        • Federal Depository
        • Homeland Security Digital Library

        About

        • Hours
        • Library Staff
        • About Us
        • Visit Us

        NPS-Licensed Resources - Terms & Conditions

        Copyright Notice

         
         

          Federal Depository Library  

        NPS Home Privacy Policy Copyright Accessibility Contact Webmaster