Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with graph-theory
Search options answers only
not deleted
user 1266
Questions about the branch of combinatorics called graph theory (not to be used for questions concerning the graph of a function). This tag can be further specialized via using it in combination with more specialized tags such as extremal-graph-theory, spectral-graph-theory, algebraic-graph-theory, topological-graph-theory, random-graphs, graph-colorings and several others.
1
vote
Accepted
Non-regular cospectral graphs with same degree sequences
Let $D$ be a Steiner triple system on $v$ points. (So $v\equiv1,3$ mod 6). The incidence
graph is the bipartite graph with the $v$ points as one colour class and the $v(v-1)/6$
blocks as the second; a …
- 4,784
3
votes
Accepted
Showing two vertices have same degree under a certain condition
I'll take $\lambda=1$ and use $E_j$ for $\mathcal{P}_j$. The $k$-th time derivative of $e^{-it(L-E_j)}s$ at $t=0$ is
\[
(-i(L-E_j))^k s.
\]
Now $(L-E_j)s = -v_j$ (because $Ls=0$) and, noting that $E_j …
- 12.1k
10
votes
Accepted
Realizing a monoid as $\mathrm{End}(G)$ for some graph $G$
Hedrlín and Pultr proved that every monoid was the endomorphism monoid of a graph. See their paper "Symmetric relations (undirected graphs) with given semigroup" Monatsh. Math 69 (1965), eudml, DOI: 1 …
- 4,713
9
votes
Accepted
Strongly rigid regular graphs
Let $X(\mathcal{S)}$ be the block graph of a Steiner triple system $\mathcal{S}$ on $v$ points. The triple system consists of $b=v(v-1)/6$ triples from a set $V$ of size $v$ such that each pair of poi …
- 4,713
2
votes
Distance regular Cayley graphs on $Z_2^n$?
A Cayley graph for $\mathbb{Z}^2_d$ with valency $m$ can always be constructed as a coset graph of a subgroup $C$ of $\mathbb{Z}^2_m$ - vertices are the cosets of $C$, cosets are adjacent if there is …
- 12.1k
4
votes
Accepted
Strongly rigid connected $k$-regular graphs
I will use the blocks of Steiner triple systems. Suppose $\mathcal{S}$ is a Steiner triple system on $v$ points. Then $v\cong1,3$ mod 6 and there are $v(v-1)/2$ blocks. The block graph has the blocks …
- 12.1k
5
votes
Non-isomorphic graphs with diameter two
A random graph $G(n,1/2)$ has diameter $2$ almost surely, and there is an integer $\ell$ such that, almost surely, its chromatic number is $\ell$
or $\ell+1$. (See Achlioptas and Naor - The two possi …
- 12.9k
7
votes
Accepted
Lovász conjecture and 2-connected graphs
The vertex connectivity of a vertex-transitive graph with valency $k$ is at least $2(k+1)/3$ (Mader/Watkins). So if you prove the conjecture for 3-connected graphs, you've done them all.
- 12.1k
9
votes
Accepted
Spectrum of an adjacency matrix
Since the eigenvalues are real, and since their sum is the trace of $A$, which is zero, we see that either all eigenvalues are zero, or there are both positive and negative eigenvalues. So no non-empt …
3
votes
Connection between graph spectra and graph homomorphisms
There does not seem to be a large overlap; the basic problem is that homomorphisms generally destroy nearly all spectral information. There are important exceptions though. Thus in https://arxiv.org/a …
- 12.1k
6
votes
Are there only finitely many distinct cubic walk-regular graphs that are neither vertex-tran...
What follows is a proof that semisymmetric graphs are walk-regular.
Say vertices $u$ and $v$ in a graph $X$ are cospectral if the graphs $X\setminus u$ and $X\setminus v$ are cospectral. If $X$ is se …
- 12.1k
6
votes
Accepted
Are there graphs whose matching polynomials are Legendre?
Any family of orthogonal polynomials can be realized as the characteristic polynomials of a sequence of weighted paths, possibly with loops. If the implicit weight function is symmetric about the orig …
- 12.1k
1
vote
What is the number of the ways of travelling through a path graph to reach a node from another?
In this particular case there is a simple approach. Take the infinite path with the integers as its vertex set. The number of walks of length $k$ starting at $0$ is $2^k$; the number of walks of lengt …
- 12.1k
4
votes
When is the adjacency algebra of a graph an association scheme?
I am not sure is this is a useful answer, but it is correct: if the graph is connected and regular, its adjacency algebra is an association scheme if and only if it is closed under Schur product. Note …
- 12.1k
2
votes
colored graph characteristic polynomial
One difficulty here is that you are asking a number of questions, none of which have short answers.
It follows from results in Chapter 5 of my "Algebraic Combinatorics" that, if you add a loop of wei …
- 12.1k