로컬 선형 그래프

그래프 이론에서 국소 선형 그래프는 모든 가장자리가 정확히 하나의 삼각형에 속하는 비방향 그래프다.동등하게, 그래프의 각 꼭지점에 대해, 그 이웃들은 각각 정확히 하나의 이웃에 인접해 있기 때문에, 이웃들은 유도 매칭으로 짝지어질 수 있다.^[1]국소 선형 그래프는 국소적으로 일치하는 그래프라고도 불린다.^[2]

로컬 선형 그래프에 대한 많은 구조는 알려져 있다.로컬 선형 그래프의 예로는 삼각형 선인장 그래프, 3-정규 삼각형이 없는 그래프의 선인장 그래프, 더 작은 로컬 선형 그래프의 데카르트 제품을 들 수 있다.특정 크네저 그래프와 강력하고 정규적인 그래프도 국소적으로 선형이다.

로컬 선형 그래프가 얼마나 많은 가장자리를 가질 수 있는지에 대한 문제는 루즈사-스제메레디 문제의 공식화 중 하나이다.밀도 그래프는 정점 수의 제곱에 비례하는 가장자리 수를 가질 수 있지만, 국소 선형 그래프는 가장자리 수가 더 적어 최소한 정점이 아닌 인자에 의해 제곱에 미치지 못한다.국소적으로 선형적일 수 있는 가장 밀도가 높은 평면 그래프도 알려져 있다.가장 밀도가 낮은 선형 그래프는 삼각형 선인장 그래프다.

시공

접착 및 제품

우정 그래프는 하나의 공유 정점에서 삼각형 집합을 함께 붙임으로써 형성된 그래프로, 국소적으로 선형이다.그것들은 모든 꼭지점 쌍(인접적이든 아니든)이 정확히 하나의 공통 이웃을 공유하는 더 강한 속성을 가진 유일한 유한 그래프다.^[3]더 일반적으로 모든 삼각형 선인장 그래프는 추가 주기를 형성하지 않고 삼각형을 정점에 붙임으로써 형성된 그래프로서 국소적으로 선형이다.^[4]

로컬 선형 그래프는 그래프에 대한 clique-sum 연산의 한 형태인 다음 연산을 통해 더 작은 로컬 선형 그래프에서 형성될 수 있다.$G{\displaystyle }$ ${\displaystyle G}$ $및{\displaystyle }$ H$$ ${\displaystyle H}$을(를) 두 개의 로컬 선형 그래프로 설정하고$$ 각 그래프에서 삼각형을 선택한 다음 선택한 두 삼각형에서 해당 쌍의 정점을 병합하여 두 그래프를 접착제로 붙이십시오.그런 다음 결과 그래프는 국소적으로 선형을 유지한다.^[5]

제품의 모든 삼각형은 하나 또는 다른 요인의 삼각형에서 나오기 때문에 두 개의 로컬 선형 그래프의 데카르트 곱은 로컬로 선형으로 유지된다.예를 들어, 9-Vertex Paly 그래프(3-3 duoprism의 그래프)는 두 삼각형의 데카르트 산물이다.^[1]해밍 그래프 $H{\displaystyle (\mathrm{d}}$ ${\displaystyle ,}$ 3${\displaystyle }$) ${\displaystyle H(d,3)}$은 $d{\displaystyle }$ ${\displaystyle d}$ 삼각형으로$$ 이루어진 데카르트 제품이며, 다시 한 번 국소적으로 선형이다.^[6]

작은 그래프에서

그 자체가 국소적으로 선형적이지 않은 일부 그래프는 더 큰 국소 선형 그래프를 구성하는 프레임워크로 사용될 수치로 사용될 수 있다.그러한 구성 중 하나는 선 그래프를 포함한다.For any graph ${\displaystyle G}$, the line graph ${\displaystyle L(G)}$ is a graph that has a vertex for every edge of ${\displaystyle G}$. Two vertices in ${\displaystyle L(G)}$ are adjacent when the two edges that they represent in ${\displaystyle G}$ have a common endpoint.$G{\displaystyle }$ ${\displaystyle G}$이(가) 3-정규 삼각형이 없는 그래프인 경우 선 $그래프{\displaystyle }$ L${\displaystyle (G}$) ${\displaystyle L(G)}$은(는) 4-정규형이고 국소적으로 선형이다$$.이 그래프는 $G{\displaystyle }$ ${\displaystyle G}$의 모든 $꼭지점{\displaystyle }$ v ${\displaystyle v}$에 대한 삼각형을 가지고 있으며, 세 개의 가장자리가 $v{\displaystyle }$ ${\displaystyle v}$에 입사하는 것과 일치하는 삼각형의 정점을 가지고 있다$.$ 모든 4개의 정규 로컬 선형 그래프는 이러한 방식으로 구성할 수 있다.^[7]예를 들어 큐보타헤드론의 그래프는 큐브의 선 그래프여서 국소적으로 선형이다.위에서 카르테시안 제품으로 구성된 국부적 선형 9-Vertex Paly 그래프 역시 효용 ${\displaystyle {그래프\mathrm{}}_{}}$ K ${\displaystyle 3_{}}$,${\displaystyle {}_{}}$3 ${\$의 선 그래프로 다른 방식으로 구성될 수 있다$.$ 피터슨 그래프의 선 그래프 역시 이 구조에 의해 국부적으로 선형이다.그것은 우리들과 유사한 특성을 가지고 있다: 가장 큰 집단이 3개의 정점을 가지고 있고, 각 정점은 정확히 2개의 가장자리 분리형 집단에 있으며, 구별되는 집단에서 가장자리를 가진 최단 주기는 길이가 5이다.^[8]

보다 복잡한 확장 프로세스는 평면 그래프에 적용된다.$G{\displaystyle }$ ${\displaystyle G}$을(를) 모든 면이 입방체 그래프와 같이 4각형인 방식으로 평면에 삽입된 평면 그래프가 되도록$$ 한다.$G{\displaystyle }$ ${\$$displaystyle G$의 각 면에 정사각형 반감증을 붙인 다음 G {\$displaystyle G}$의 원래 가장자리를 삭제하면 새 로컬 선형 평면 그래프가 생성된다$.$결과의 가장자리와 꼭지점의 수는 오일러의 다면식으로부터 계산할 수 있다: $G{\displaystyle }${\$displaystyle G$$}$에 $정점$이${\displaystyle }n이면{\displaystyle }$ ${\displaystyle \mathrm{정확히}}$ n - 2 {\$displaystyle$ $n-2}$면들이$$ $,$ G {\$displaystyle g}$의 면들을 항정신병합체들에 의해$$ 교체한 결과는 $5{\displaystyle \mathrm{}}$(${\displaystyle n}$- ${\displaystyle 2}$)${\displaystyle }$+ 2$${$displaysty$)이다.$le 5(n-2)+2}$개의$$ 꼭지점과 ${\displaystyle 12(\mathrm{n}}$ ${\displaystyle -}$ 2${\displaystyle }$) ${\displaystyle 12(n-2)}$개의$$ 가장자리.^[5]예를 들어 큐옥타헤드론은 4사이클의 두 얼굴(내외면)에서 다시 이런 방식으로 생산될 수 있다.이 구조물의 제거된 4 사이클은 큐옥타헤드론에서 사각면 4개의 대각선이 다면체를 이등분하는 사이클로 볼 수 있다.

대수구축

동일한 크기 집합의 교차 패턴으로 구성된 그래프인 특정 크네저 그래프는 로컬로 선형이다.크네저 그래프는 두 개의 매개변수, 즉 그들이 나타내는 집합의 크기와 이들 집합이 그려진 우주의 크기로 설명된다.Kneser 그래프 ${\displaystyle K_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle a_{}}$ ,${\displaystyle {}_{}}$b ${\$에는 ${\displaystyle$ a} -element $집합$의 b {\displaystyle $b}$ $-element$$$ subset를 나타내는${\displaystyle }$(${\displaystyle \genfrac{}{}{0ex}{}{b}{})}$ ${\displaystyle$ {$a}{b$}} 정점$($이항계수의 표준 표기법)이 있다.이 그래프에서 해당 하위 집합이 분리 집합일 때 두 꼭지점이 인접하여 공통 요소가 없다.$a{\displaystyle }$= ${\displaystyle 3}$ ${\displaystyle b}$ ${\displaystyle a=3b$인 특별한 경우, 결과 그래프는 로컬로 선형이 된다. 두 개의 분리된 $b{\displaystyle }$ ${\displaystyle$ $b$$}$ -element$$ $subsets{\displaystyle }$ X ${\\displaystyle$ $X$$}$ 및 $Y$ ${\\displaystyle Y}$에 대해 두 개 모두 정확히 하나의 $다른{\displaystyle }$ b ${\displaysty$ subsetset이 있기 때문이다$.$ll the elements that are neither in ${\displaystyle X}$ nor in ${\displaystyle Y}$. The resulting locally linear graph has ${\displaystyle {\tbinom {3b}{b}}}$ vertices and ${\displaystyle {\tfrac {1}{2}}{\tbinom {3b}{b}}{\tbinom {2b}{b}}}$예를 들어, ${\displaystyle \mathrm{b}}$= 2 ${\displaystyle b=2}$의 경우 Kneser 그래프 $K{\displaystyle }$ G ${\displaystyle {6\mathrm{}}_{}}$,${\displaystyle 2_{}}$ ${\$개는 정점 15개와 가장자리 45개로 로컬 선형이다$$.^[2]

국소 선형 그래프는 진행 없는 숫자 집합에서 구성할 수도 있다.$p{\displaystyle }$ ${\displaystyle p}$을(를) 프라임 숫자로 하고$$$$, $A{\displaystyle }${\$displaystyle$$A$$}$의 세 멤버가 산술 추이 $모듈$로 p ${\displaystyle p}$을(를) 형성하지 않도록$$ A ${\displaystystyle A}$을(를)를 모듈로 $설정$한다.$(\displaystyle$ p$})$이 세트는 ${\displaystyle \mathrm{3p}}$ ${\$$displaystyle$ $3p}$ 정점과$$ $p$ ${\displaystyle 로컬}$ $선형$인${\displaystyle }$3자형$$ 그래프를 $구성$하는 데 사용할 수 있다$.$이 그래프를 구성하려면 $각각{\displaystyle \mathrm{}}$ 0 ${\displaystyle 0$$}$에서 $p{\displaystyle }$-$$까지 번호가 매겨진 정점 세 개를 만드십시오$.$ $0{\displaystyle \mathrm{}}$ ${\displaystyle$ 0$}$에서 $p{\displaystyle }$-$$까지 범위에$$ 있는$$ 각 $숫자{\displaystyle }$ x$${\$displaystyle p-1$$}$ 및 각 $요소$에 $대해{\displaystyle }$ A ${\displaystystyle$ A$}$의 {\$displaystystystystystystystystystystystyleasestyone$ a$}$을(으$)$를 controlleasestylease styleasestytemptionsty정점 집합의 첫 번째$$ 정점 집합에서 정수점 $x{\displaystyle }$ ${\displaystyle$ x$}$을(를) 연결하는 삼각형, 정점 집합의$$ 두 번째 정점 집합에서$$ $숫자{\displaystyle }$ $x{\displaystyle }$+ ${\displaystyle a}$ ${\displaystyle x+a}$을(를) 연결하는 정점 x +${\displaystyle 2}$ ${\displaystyle a}$ ${\displaysty x+2a}$을(를)로 한다.이 삼각형들의 조합으로 그래프를 만들어라.삼각형의 조합이기 때문에 결과 그래프의 모든 가장자리는 삼각형에 속한다.그러나 이런 식으로 형성된 삼각형 외에 다른 삼각형은 있을 수 없다.Any other triangle would have vertices numbered ${\displaystyle (x,x+a,x+a+b)}$ where ${\displaystyle a}$, ${\displaystyle b}$, and ${\displaystyle c=(a+b)/2}$ all belong to ${\displaystyle A}$, violating the assumption that there be no arithmetic progressions ${\displaystyle (}$$a{\displaystyle }$${\displaystyle }$, ${\displaystyle c}$, ${\displaystyle b}$) ${\$$displaystyle A}$의 {\$displaystyle (a,c,b$$)\}.$^[9] 예를 들어 $p{\displaystyle }$= ${\displaystyle 3}$ ${\displaystyle p=3}$ $및$ A${\displaystyle }$=${\displaystyle }${${\displaystyle }$± ${\displaystyle 1\}}$ ${\displaystysty$ A$=\\\\\\pm$1$\}$을 사용하여 이 $구조$의 결과는 9-Vertex Paly 그래프가 된다.

규칙성

정점이 거의 없는 일반 그래프

그래프는 모든 정점이 인시던트 가장자리 수인 동일한 정도를 가질 때 규칙적이다.각 정점의 가장자리는 삼각형으로 쌍을 이룰 수 있기 때문에 모든 국소 선형 그래프는 각 정점에서 짝수도를 가져야 한다.두 개의 국소 선형 정규 그래프의 데카르트 산물은 다시 국소적으로 선형적이고 정규적이며, 인자의 수준의 합과 같다.따라서 2도(삼각형)의 국소 선형 그래프로 이루어진 카르테시안 제품을 사용하여 모든 고른 정도의 국소 선형 그래프를 정기적으로 생성할 수 있다.^[1]

2 ${\displaystyle r}$ ${\displaystyle 2r}$ - 정규$$ 로컬 선형 그래프에는 최소 ${\displaystyle 6}$ ${\displaystyle \mathrm{r}}$- 3 ${\displaystyle 6r-3}$의 정점이 있어야 하며, 이는 모든 삼각형과 그 인접 영역에만 정점이 많기 때문이다.(삼각형의 어떤 두 꼭지점도 로컬 선형성을 위반하지 않고 이웃을 공유할 수 없다.)정점이 정확히 이만큼 많은 일반 그래프는 $r{\displaystyle }$ ${\displaystyle r}$이(가) 1, 2, 3 또는 5이고 이 네 가지 사례 각각에 대해 고유하게 정의된 경우에만 가능하다.The four regular graphs meeting this bound on the number of vertices are the 3-vertex 2-regular triangle ${\displaystyle K_{3}}$, the 9-vertex 4-regular Paley graph, the 15-vertex 6-regular Kneser graph ${\displaystyle KG_{6,2}}$, and the 27-vertex 10-regular complement graph of the Schläfli graph.또한 최종 27-Vertex 10-정규 그래프는 입방면 27개의 선에 대한 교차 그래프를 나타낸다.^[2]

매우 정규 그래프

매우 정규적인 그래프는 파라미터의 4배$({\displaystyle n,}$ ${\displaystyle k,}$ ${\displaystyle \lambda }$,${\displaystyle \mu }$) ${\displaystyle$($n$$,k,\lambda ,\mu$)로 특징지어질 수 있는데, 여기서$$ $n{\displaystyle }$ ${\\$$displaystyle k}$은 정점당 입사 에지 수이고, $k{\displaystyle }$ ${\displaystylease \lamda }$은 각 정점에 대한 공유 이웃의 수입니다.정점의 djacenter 쌍, $\mu {\displaystyle }$ ${\displaystyle \mu }$은(는) 모든 정점의 쌍에 대한 공유 인접 수입니다.$\lambda {\displaystyle }$= ${\displaystyle 1}$ ${\displaystyle \lambda =1}$인 경우 그래프는$$ 로컬로 선형이다.위에서 이미 언급된 국소 선형 그래프는 강력한 정규 그래프와 그 모수는^[10]

• 삼각형(3,2,1,0),
• 9-Vertex Paley 그래프(9,4,1,2)
• Kneser 그래프 ${\displaystyle {\mathrm{K}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {6\mathrm{}}_{}}$,${\displaystyle {}_{}}$2 ${\$,3$}($15,$$6,6,3),
• Schléfli 그래프의 보완(27,10,1,5)

다른 국소 선형 강력 정규 그래프에는 다음이 포함된다.

• 브루워-헤이머 그래프(^[11]81,20,1,6)
• Berlekamp-van Lint-Si델 그래프(243,22,1,2),^[12]
• 코시덴테-펜틸라 그래프(378,52,1,8),^[13]
• 게임 그래프(729,112,1,20).^[14]

$\lambda {\displaystyle }$= ${\displaystyle 1}$ ${\displaystyle \lambda =$1}을$($를) 사용하여 잠재적으로 유효성이 있는 다른 조합에는 (99,14,1,2) 및 (115,18,1,33)이$$ 포함되지만 이러한 매개변수를 가진 강력한 정규 그래프가 존재하는지 여부는 알 수 없다.^[10]매개변수(99,14,1,2)가 있는 강력 정규 그래프의 존재에 대한 문제는 콘웨이의 99그래프 문제로 알려져 있으며, 존 호튼 콘웨이는 그 해법에 대해 1000달러의 상금을 내걸었다.^[15]

거리 정규 그래프

국소적으로 선형인 4도나 6도의 거리 정규 그래프가 상당히 많다.같은 정도의 강력한 정규 그래프 외에도 피터슨 그래프의 선 그래프, 해밍 그래프 $H{\displaystyle (}$3${\displaystyle ,}$ ${\displaystyle 3}$) ${\displaystyle H(3,3$ 절반으로 줄어든 포스터 그래프도 포함된다.^[16]

밀도

Ruzsa-Szemerédi 문제의 한 공식은 $n{\displaystyle }$ ${\displaystyle n}$ -vertex$$ 로컬 선형 그래프에서 최대 에지 수를 요구한다.Imre Z로. Ruzsa와 Endre Szemerédi가 증명했으므로 이 최대 숫자는 ${\displaystyle (}$n ${\displaystyle {2\mathrm{}}^{}}$) ${\displaystyle o(n$$^{2-\varepsilon }})$이지만 매 > ${\displaystyle \varepsilon$ >$0}$에 대해 $\Omega {\displaystyle \mathrm{}}$ ($n$ 2 -$\)$이다진행 없는 집합에서 로컬 선형 그래프를 구성하면 n ${\displaystyle {2\mathrm{}}^{}}$/ ${\displaystyle \exp }$ ${\displaystyle }$ ${\displaystyle O}$( ${\displaystyle \sqrt{\mathrm{로그}\log }}$ n )${\displaystyle$ n$^{2}/\exp O({\sqrt {\logn})}$개의 가장자리가$$ 있는 알려진 가장 밀도가 높은 로컬 선형 그래프로 이어진다.(이러한 $공식$에서$$o {\$displaystyle$o},$$$\Omega {\displaystyle \mathrm{}}${\$displaystyle \Oomega$ $o{\displaystyle }${\$displaystyle$ O$}$^[9]은 각각 little o 표기법, big Omega 표기법, big O 표기법의 예들이다$$.)

평면 그래프 중에서 $정점$이 n ${\displaystyle n}$인 로컬 선형 그래프에서 최대 에지 수는 ${\displaystyle \frac{12}{}}$ ${\displaystyle \frac{5}{}(n}$- ${\displaystyle 2}$ $){\displaystyle {\tfrac {12}{5}}($n-2)이다$.$The graph of the cuboctahedron is the first in an infinite sequence of polyhedral graphs with ${\displaystyle n=5k+2}$ vertices and ${\displaystyle {\tfrac {12}{5}}(n-2)=12k}$ edges, for ${\displaystyle k=2,3,\dots }$, constructed by expanding the quadrilateral faces of ${\displaystyle K_{}}$${\displaystyle 2_{}}$,${\displaystyle k_{}}$ ${\$ 반격으로$$.이러한 예는 12 ${\displaystyle \frac{5}{}(\mathrm{n}}$- 2 )${\displaystyle {\tfrac {12}{5}(n-2)}$ 상한을 달성할$$ 수 있음을 보여준다.^[5]

모든 로컬 선형 그래프에는 일치 항목이 제거된 후에도 연결된 상태로 유지되는 특성이 있는데, 이는 그래프를 통과하는 어떤 경로에서 각 일치된 가장자리는 삼각형의 다른 두 가장자리로 대체될 수 있기 때문이다.이 특성이 있는 그래프 중 가장 밀도가 낮은 그래프는 삼각형 선인장 그래프인데, 이 그래프 역시 국소적으로 가장 밀도가 낮은 선형 그래프다.^[4]

참조