Some properties of edge intersection graphs of single bend paths on a grid |
| |
| Institution: | 1. Department of Biomedical and Health Information Sciences, College of Applied Health Sciences, University of Illinois at Chicago, 1919 W Taylor St., Chicago, IL 60612, United States;2. Department of Health System Science, College of Nursing, University of Illinois at Chicago, 845 South Damen Ave, Chicago, IL 60612, United States;3. Department of Computer Science, College of Engineering, University of Illinois at Chicago, 851 South Morgan Street, Chicago, IL 60607, United States;4. Department of Health Care Environments and Systems, College of Nursing, University of Florida, PO Box 100187, Gainesville, FL 32610, United States;5. Department of Medicine, College of Medicine, University of Arizona, 1501 N. Campbell Dr, Tucson, AZ 85724, United States;6. The University of Arizona Health Sciences Center, 1295 North Martin Ave, Tucson, AZ 85721, United States;1. Department of Mathematics, The Madura College, Madurai 625 011, India;2. Department of Mathematics, St. Xavier’s College, Palayamkottai 627 002, India;1. Caesarea Rothschild Institute and Department of Computer Science, University of Haifa, Mount Carmel, Haifa 31905, Israel;2. PSL, Université Paris-Dauphine, 75775 Paris Cedex 16, France;3. CNRS, LAMSADE UMR 7243, France |
| |
| Abstract: | We consider the family of intersection graphs G of paths on a grid, where every vertex v in G corresponds to a single bend path Pv on a grid, and two vertices are adjacent in G if and only if the corresponding paths share an edge on the grid. We first show that these graphs have the Erdös-Hajnal property. Then we present some properties concerning the neighborhood of a vertex in these graphs, and finally we consider some subclasses of chordal graphs for which we give necessary and sufficient conditions to be edge intersection graphs of single bend paths in a grid. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
