{
  "id": "1405.6527",
  "version": "v1",
  "published": "2014-05-26T10:06:35.000Z",
  "updated": "2014-05-26T10:06:35.000Z",
  "title": "A study of link graphs",
  "authors": [
    "Bin Jia"
  ],
  "comment": "This is for the presentation at Discrete Maths Research Group Seminar, Monash University, 30 May 2014",
  "categories": [
    "math.CO"
  ],
  "abstract": "Graph theory is a branch of mathematics in which pair-wise relations between objects are studied. My PhD thesis, supervised by David R. Wood, introduces and investigates a new family of graphs, called link graphs, that generalises the notions of line graphs and path graphs. An s-link is a walk of length s such that consecutive edges are different. The s-link graph of a given graph G is the graph with vertices the s-links of G, and two vertices are adjacent if their corresponding s-links form an (s + 1)-link; Or equivalently, one corresponding s-link can be shunted to the other in one step. For example, the 1-link graph of G is the line graph of G. We give a characterisation for link graphs, which leads to algorithmic solutions to their recognition and determination problems, and implies that the recognition problem belongs to NP. Moreover, based on a recursive structure of linkgraphs, we obtain results about the chromatic number, Hadwiger number and isomorphism group of link graphs. We also obtain results about the uniqueness, tree-decomposition and better-quasi-ordering of the original graphs of a given link graph.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-05-26T10:06:35.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "line graph",
      "recognition problem belongs",
      "path graphs",
      "s-link graph",
      "corresponding s-links form"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1405.6527J"
    }
  }
}