<p>A graph <i>G</i> is called a cap graph if <i>G</i> represents the intersection graph of a family of spherical caps with the same angular radius. The complement of a graph <i>G</i>, denoted by <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\bar{G}\)</EquationSource> <EquationSource Format="MATHML"><math> <mover accent="true"> <mrow> <mi>G</mi> </mrow> <mrow> <mo stretchy="false">¯</mo> </mrow> </mover> </math></EquationSource> </InlineEquation>, is a graph with the same vertex set as <i>G</i> in which two vertices are adjacent only when they are non-adjacent in <i>G</i>. We prove that for any tree <i>T</i>, there is a real number <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\delta \in (0,\pi /2)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>δ</mi> <mo>∈</mo> <mo stretchy="false">(</mo> <mn>0</mn> <mo>,</mo> <mi>π</mi> <mo stretchy="false">/</mo> <mn>2</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> such that the complement of <i>T</i> is a cap graph of angular radius <i>d</i> for every <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(d\in (\delta , \pi /2)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>d</mi> <mo>∈</mo> <mo stretchy="false">(</mo> <mi>δ</mi> <mo>,</mo> <mi>π</mi> <mo stretchy="false">/</mo> <mn>2</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. We also classify all types of complete bipartite graphs that are cap graphs. For every such type we determine the range of angular radius of the spherical caps.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On Intersection Graphs of Spherical Caps

  • Hiroshi Maehara,
  • Horst Martini

摘要

A graph G is called a cap graph if G represents the intersection graph of a family of spherical caps with the same angular radius. The complement of a graph G, denoted by \(\bar{G}\) G ¯ , is a graph with the same vertex set as G in which two vertices are adjacent only when they are non-adjacent in G. We prove that for any tree T, there is a real number \(\delta \in (0,\pi /2)\) δ ( 0 , π / 2 ) such that the complement of T is a cap graph of angular radius d for every \(d\in (\delta , \pi /2)\) d ( δ , π / 2 ) . We also classify all types of complete bipartite graphs that are cap graphs. For every such type we determine the range of angular radius of the spherical caps.