home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / math / 15373 < prev    next >
Encoding:
Text File  |  1992-11-22  |  908 b   |  25 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!cs.utexas.edu!sun-barr!ames!haven.umd.edu!darwin.sura.net!Sirius.dfn.de!news.uni-bielefeld.de!unibi!umatf071
  3. From: umatf071@unibi.hrz.uni-bielefeld.de (0105)
  4. Subject: the rang of cographs
  5. Message-ID: <1992Nov22.191921.26033@unibi.hrz.uni-bielefeld.de>
  6. Date: Sun, 22 Nov 92 19:19:21 GMT
  7. Organization: Universitaet Bielefeld
  8. Keywords: cograph, rang
  9. Lines: 14
  10.  
  11. Cographs are the graphs formed from a single vertex under the closure
  12. of the operations of union and complement. Another characterization of 
  13. cographs is that they are the undirected graphs with no induced paths
  14. on four vertices (P_4). (see: Corneil, ..., SIAM J Comput 14 (1985) 926)
  15.  
  16. Let A(G) be the adjacency matrix of the graph G.
  17.  
  18. Conjecture:
  19.   For a cograph G there is
  20.   rg( A(G) ) = the number of different nonzero columns of A(G).
  21.  
  22. Are there other classes of graphs with this property?
  23.  
  24. Torsten Sillke
  25.