강한 정규 그래프
그래프 이론에서 강한 정규 그래프는 정규 그래프 중 각 꼭지점 쌍의 공통 이웃의 개수에 대해 추가적인 조건을 가지는 그래프이다. G = (V, E)를 정점 v개를 가지는 k-정규 그래프라고 할 때, 어떤 정수 λ, μ가 존재하여 다음 조건을 만족할 경우 G를 강한 정규 그래프라고 한다.
- 모든 인접한 꼭짓점 쌍은 λ개의 공통 이웃을 갖는다.
- 모든 인접하지 않은 꼭짓점 쌍은 μ개의 공통 이웃을 갖는다.
이 조건을 만족하는 그래프를 srg(v, k, λ, μ)으로 쓰기도 한다. 강한 정규 그래프는 1963년 라지 찬드라 보스에 의해 도입되었다.[1]
일부 저자는 동일한 크기 완전 그래프들의 서로소 합집합[2][3] 또는 그 여 그래프와 같이 정의를 자명하게 충족시키는 그래프를 제외하기도 한다.
srg(v, k, λ, μ)의 여 그래프는 srg(v, v − k − 1, v − 2 − 2k + μ, v − 2k + λ)으로, 강한 정규 그래프이다.
μ가 0이 아닌 강한 정규 그래프는 직경이 2인 거리 정규 그래프이다. λ = 1인 강한 정규 그래프는 국소적 선형 그래프이다.
성질
편집매개변수 간의 관계
편집srg(v, k, λ, μ)의 4개 매개변수는 독립적이지 않고, 다음 관계를 따라야 한다.
위의 관계는 다음과 같은 조합론적 논증을 통해 도출할 수 있다.
- 그래프의 꼭짓점이 3개의 깊이에 있다고 상상하자. 깊이 0에 있는 정점 하나를 뿌리로 선택한다. 이 정점의 k개의 이웃은 깊이 1에 있고, 다른 모든 정점은 깊이 2에 있다.
- 깊이 1인 꼭짓점은 뿌리에 직접 연결되므로 뿌리와 공통되는 다른 이웃 λ개가 있어야 하고, 이러한 공통 이웃은 깊이 1에 있어야 한다. 각 꼭짓점의 차수가 k 이므로 깊이 2 꼭짓점에 연결하기 위한 깊이 1 꼭짓점에 남아 있는 변은 개이므로, 깊이 1과 깊이 2 사이에는 변 개가 존재한다.
- 깊이 2 꼭짓점은 뿌리에 직접 연결되지 않으므로 뿌리와 μ개의 공통 이웃이 있어야 하고, 이러한 공통 이웃은 모두 깊이 1에 있어야 한다. 깊이 2에는 꼭짓점이 개 있고, 각각은 깊이 1 꼭짓점 μ 개와 연결되므로 깊이 1과 깊이 2 사이에는 변 개가 존재한다.
- 깊이 1과 깊이 2 사이에 있는 변 개수에 대한 두 식을 등호로 연결하여 를 얻는다.
인접행렬
편집I를 단위행렬, J를 요소가 모두 1인 v × v 행렬이라고 하자. 강한 정규 그래프의 인접행렬 A는 두 방정식을 만족한다.
이는 정규 그래프 조건을 간단하게 다시 기술한 것이다. 이것은 k 가 all-one 고유 벡터를 갖는 인접 행렬의 고유값임을 보여준다. 두 번째는 강한 정규성을 나타내는 이차방정식
이다. 좌변의 ij 번째 요소는 i에서 j 까지의 길이 2인 경로의 수이다. 우변의 첫 번째 항은 i에서 자기 자신으로의 경로 수, 즉 자신의 각 이웃에 대해 i에서 이웃으로 갔다가 다시 i로 돌아오는 경로 k개이다. 두 번째 항은 i 와 j 가 직접 연결된 경우 길이 2인 경로의 수를 나타낸다. 세 번째 항은 i 와 j 가 연결되지 않은 경우 길이 2인 경로의 수이다. 세 가지 경우가 상호 배타적이고 집합적으로 완전하므로 위와 같은 등식이 성립한다.
반대로, 인접 행렬이 위의 두 조건을 모두 만족하고 완전 그래프 또는 빈 그래프가 아닌 그래프는 강한 정규 그래프이다.[4]
고윳값
편집그래프의 인접 행렬에는 정확히 3개의 고윳값이 있다.
- k, 중복도 1
- 중복도
- 중복도
중복도는 정수여야 하므로 위 표현은 크레인 조건 과 관련된 v, k, μ 및 λ 값에 대한 추가 제약을 준다.
인 강한 정규 그래프는 중복도가 같지 않은 정수 고유값을 가진다.
인 강한 정규 그래프는 대칭 회의 행렬과의 연결 때문에 회의 그래프라고 한다. 매개변수는 다음으로 감소한다.
반대로, 3개의 고유값만을 가지는 연결된 정규 그래프는 강한 정규 그래프이다.[5]
예
편집- 길이 5인 순환 그래프는 srg(5, 2, 0, 1)이다.
- 페테르센 그래프는 srg(10, 3, 0, 1)이다.
- Clebsch 그래프는 srg(16, 5, 0, 2)이다.
- Shrikhande 그래프는 거리 전이 그래프가 아닌 srg(16, 6, 2, 2)이다.
- n × n 룩 그래프, 즉 균형 잡힌 완전 이분 그래프 Kn, n 의 선 그래프는 srg(n2, 2 n - 2, n - 2, 2)이다. n = 4일 때, 매개변수는 Shrikhande 그래프의 매개변수와 같지만 두 그래프는 동형이 아니다.
- 완전 그래프 Kn의 선 그래프는 이다.
- Chang 그래프는 srg(28, 12, 6, 4)로 매개변수가 K8의 선 그래프와 같지만 이 4개의 그래프는 동형이 아니다.
- 일반화된 사변형 GQ(2, 4)의 선 그래프는 srg(27, 10, 1, 5)이다. 사실 모든 일반화된 차수(s, t)의 사각형은 다음과 같은 방식으로 강한 정규 그래프를 제공한다. 즉, srg((s + 1)(st + 1), s(t + 1), s − 1, t + 1).
- Schläfli 그래프는 srg(27, 16, 10, 8)이다.[6]
- 호프만-싱글턴 그래프는 srg(50, 7, 0, 1)이다.
- Sims-Gewirtz 그래프는 (56, 10, 0, 2)이다.
- M22 그래프는 srg(77, 16, 0, 4)이다.
- Brouwer-Haemers 그래프는 srg(81, 20, 1, 6)이다.
- 히그먼-심스 그래프는 srg(100, 22, 0, 6)이다.
- 국소 매클로플린 그래프는 srg(162, 56, 10, 24)이다.
- Cameron 그래프는 srg(231, 30, 9, 3)이다.
- Berlekamp-van Lint-Seidel 그래프는 srg(243, 22, 1, 2)이다.
- 매클로플린 그래프는 srg(275, 112, 30, 56)이다.
- 차수 q 의 페일리 그래프는 srg(q, (q - 1)/2, (q - 5)/4, (q - 1)/4)이다. 가장 작은 페일리 그래프(q = 5인 경우)는 5-순환 그래프이다.
- 자기 보완 호 전이 그래프는 강한 정규 그래프이다.
강한 정규 그래프와 그 여 그래프가 모두 연결되어 있는 경우 원시적이라고 한다. 위에서 제시된 모든 그래프는 원시적이다. 원시적이지 않은 강한 정규 그래프는 μ = 0 또는 λ = k 의 매개변수를 가진다.
콘웨이의 99-그래프 문제는 srg(99, 14, 1, 2)의 구성을 묻는 문제이다. 이러한 매개변수가 있는 그래프가 존재하는지 여부는 알려져 있지 않으며 존 호턴 콘웨이는 이 문제에 대한 해결책으로 1000달러의 상금을 제안하였다.[7]
같이 보기
편집각주
편집- ↑ https://projecteuclid.org/euclid.pjm/1103035734, R. C. Bose, Strongly regular graphs, partial geometries and partially balanced designs, Pacific J. Math 13 (1963) 389–419. (p. 122)
- ↑ Brouwer, Andries E; Haemers, Willem H. Spectra of Graphs. p. 101 보관됨 2012-03-16 - 웨이백 머신
- ↑ Godsil, Chris; Royle, Gordon. Algebraic Graph Theory. Springer-Verlag New York, 2001, p. 218.
- ↑ Cameron; Peter, Jephson, 《Designs, graphs, codes, and their links》, Cambridge University Press
- ↑ Godsil, Chris; Royle, Gordon. Algebraic Graph Theory. Springer-Verlag, New York, 2001, Lemma 10.2.1.
- ↑ Weisstein, Eric Wolfgang. “Schläfli graph”. 《Wolfram MathWorld》 (영어). Wolfram Research.
- ↑ 존 호턴 콘웨이, 《Five $1,000 Problems (Update 2017)》 (PDF), Online Encyclopedia of Integer SequencesJohn Horton Conway
참고 문헌
편집- AE Brouwer, AM Cohen 및 A. Neumaier(1989), Distance Regular Graphs. 베를린, 뉴욕: Springer-Verlag.ISBN 3-540-50619-5ISBN 3-540-50619-5 ,ISBN 0-387-50619-5
- Chris Godsil 및 Gordon Royle(2004), Algebraic Graph Theory. 뉴욕: Springer-Verlag.ISBN 0-387-95241-1ISBN 0-387-95241-1
외부 링크
편집- Eric W. Weisstein, Mathworld 기사, 다양한 예.
- Gordon Royle, 더 큰 그래프족 목록.
- Andries E. Brouwer, 강한 정규 그래프의 매개변수.
- Brendan McKay, 일부 그래프 모음.
- Ted Spence, 최대 64개의 정점에 대한 강한 정규 그래프.