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 not deleted
user 18606
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
Triange-free graph and its complement has Lovász number > 3
Define $H_{n,k}$ to be the Cayley graph for $\mathbb{Z}_2^n$ whose connection set consists of all elements containing $k$ 1's. If $k$ is odd then this graph is bipartite, and if $k$ is even and $k < n …
- 2,339
2
votes
Accepted
Critical graphs and endomorphisms
There are lots of examples. They even have a name for when a graph has only surjective endomorphisms, such a graph is called a core. In fact every graph is homomorphically equivalent (has a homomorphi …
- 2,339
4
votes
Accepted
Contracting non-adjacent points in the icosahedron
No.
The icosahedron graph is distance transitive, meaning that for any two pairs $(a,b)$ and $(c,d)$ of vertices of the icosahedral graph such that $\text{dist}(a,b) = \text{dist}(c,d)$, there is an …
- 2,339
3
votes
Do graphs with $\omega(G) = \chi(G)$ grow "common" as $|V|$ grows large?
As @Ilya says, the limit is zero due to the asymptotic size of maximum cliques/independent sets. However, there is another way to see this using endomorphisms (homomorphisms from a graph to itself).
…
- 2,339
3
votes
0
answers
131
views
Asymmetric graphs stable under 3-dimensional Weisfeiler-Leman
The $k$-dimensional Weisfeiler-Leman algorithm ($k$-WL) is a method for partitioning the $k$-tuples of vertices of a graph $G$ in an approximation of the orbits of the automorphism group $\mathrm{Aut} …
- 2,339
5
votes
A graph spectra problem?
The adjacency matrix of the product is $A_1 \otimes J + I \otimes A_2$, where $J$ is the all ones matrix of size $n = |V(G_2)|$ and $I$ is the identity matrix of size $m = |V(G_1)|$. The two matrices …
- 2,339
3
votes
Accepted
Product of critical graphs and Hedetniemi's conjecture
It doesn't imply that the categorical product of critical graphs is critical, and this is not true. For instance, the complete graph on three vertices, $K_3$, is 3-critical, but $K_3 \times K_3$ is no …
- 2,339
1
vote
Accepted
Largest edge set compatible with graph endomorphisms
No. In this paper the define the hull of a graph $G$. The hull of $G$ has the same vertices of $G$ and has an edge between any pair of vertices that cannot be identified by any endomorphism of $G$. In …
- 2,339
4
votes
Accepted
Infinite connected $k$-regular graphs
Take an $n$-cycle, add an infinite tree of the right degree at each vertex of the cycle (the vertex on the cycle having degree 2 less in the tree than the other vertices of the tree). This has only on …
- 2,339
7
votes
Accepted
Projective graphs
No.
Let $P$ be any graph with $\chi(P) = n > 2$. Let $B = K_n$ and let $A$ be $K_{n,n}$ minus a perfect matching $M = \{(c_i,d_i): i \in [n]\}$. A surjective homomorphism $s : A \to B$ is given by ma …
- 2,339
3
votes
Accepted
Commutative graph product with multiplicative independence number?
The "disjunctive" or "OR" product works (see https://en.wikipedia.org/wiki/Graph_product). For graphs $G$ and $H$, define $G * H$ as the graph with vertex set $V(G) \times V(H)$, with two vertices $(g …
- 2,339
6
votes
Accepted
Does the clique-coclique bound hold for all walk-regular graphs?
EDIT: The answer is no, see comment below.
In every case I know of, the clique-coclique bound can be proven for a class of graphs by proving the stronger fact that $\vartheta(G)\bar{\vartheta}(G) \le …
- 2,339
6
votes
1
answer
255
views
Has anyone seen this graph construction that is similar to the line graph?
Given a graph $G$, its line graph, denoted $L(G)$, is the graph whose vertices are the edges of $G$ and where two edges of $G$ are adjacent in $L(G)$ if they are incident to each other, i.e., they sha …
- 2,339
2
votes
The bipartite double of two regular graphs
Also the bipartite double covers of the Shrikhande graph and the 4x4 Rook graph (i.e., the cartesian product of $K_4$ with itself) are isomorphic. Both of these graphs are 6-regular.
- 2,339
8
votes
Graph homomorphisms and line graph
Things are even worse than you imagine.
Tony's answer shows that the homomorphism order of line graphs can be partitioned into intervals whose endpoints are the complete graphs. I made use of this fa …
- 2,339