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 questions only
not deleted
user 1737
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.
7
votes
1
answer
403
views
Induced subgraphs of small strongly regular graphs
Consider a strongly regular graph $G$ with parameters $(76,30,8,14).$ Hoffman's bound tells us that $\overline{G}$ has an independent set of size at most $4$ and its not hard to see there are indeed $ …
- 3,463
4
votes
0
answers
246
views
Applying the amplification trick + probabilistic method on connected graphs
First of all, I apologise if my question is not very specific. I am not really looking for a concrete answer but rather some hints and pointers what could be used/applied in this situation. A concrete …
- 3,463
7
votes
3
answers
1k
views
Randomly contracting edges of a graph - expected number of vertices?
Let $G'$ be a graph obtained from $G$ after contracting each edge with probability $p$. Let $n = |V(G)|, e = |E(G)|$.
I would like to compute (or at least obtain a lower bound) for $E[|V(G')|]$ in te …
- 3,463
2
votes
3
answers
240
views
Regular graphs whose neighbourhoods induce matchings
Studying some problem I've arrived to the following notion.
Let a $2r$-regular graph $G$ be called neighbour-matching if $N(v) = rK_2.$ In other words, the neighbourhood of any vertex induces a matc …
- 3,463
2
votes
1
answer
244
views
Graphs of order n with a Laplacian eigenvalue of multiplicity n-1.
I suspect this could be an easy one but I am not an expert in algebraic graph theory.
Let $Q(G)$ define the Laplacian matrix for a simple graph $G$. It is well known that n is an eigenvalue of $Q(K_n …
- 3,463
5
votes
1
answer
283
views
Connected graphs that are not 2 connected
In the great book by Harary and Palmer (Graphical Enumeration) one can find many interesting things about graph asymptotics.
For example it is stated that the number of all unlabeled graph is $\sim …
- 3,463
1
vote
0
answers
76
views
Proper edge colorings with no bi-colored 5-paths
Consider you want to properly edge color a graph such that it has no bi-colored cycle. Denote by $\alpha'(G)$ the least number of colors required to color the edges of $G$ in such a way.
It is well k …
- 3,463
6
votes
1
answer
685
views
Probability that a random edge coloring of the complete graph is proper
This is a repost of this math.se question that I am posting here since it received no attention there.
What is the probability that a random edge coloring of $K_n$ with
$m \geq n$ colors resul …
- 3,463
5
votes
0
answers
319
views
Graphs with many positive eigenvalues of their distance matrix
Let $G$ be a simple connected graph $D(G)$ its distance matrix and $n_{+}(G), n_{-}(G)$ the number of positive and negative eigenvalues of $D(G)$ respectively.
We call a graph $G$ optimistic if $n_{+ …
- 3,463
1
vote
1
answer
372
views
Definition of convex cycles
Consider the following definition.
Let $C$ be a cycle of a simple graph $G$. We say that $C$ is convex if for any pair of distinct vertices $u,v \in V(C)$ $$ d_C(u,v) < d_{G-C}(u,v).$$
Is there any …
- 3,463
11
votes
1
answer
968
views
Is every matching of the hypercube graph extensible to a Hamiltonian cycle
Given that $Q_d$ is the hypercube graph of dimension $d$ then it is a known fact (not so trivial to prove though) that given a perfect matching $M$ of $Q_d$ ($d\geq 2$) it is possible to find another …
- 3,463
3
votes
3
answers
3k
views
Laplacian spectrum for product graphs
Let $G$ and $H$ be simple graphs.
I am interested in the Laplacian spectrum for various products of $G$ and $H$ namely the cartesian product, tensor product, lexicographical product and strong product …
- 3,463
4
votes
3
answers
240
views
Almost all graphs have a subgraph from a large class of graphs with constant order
I will pose the question in relation to trees but the more general question that can be deduced from the title of this post is also very interesting.
I suspect the question might have a very trivial …
- 3,463
5
votes
2
answers
780
views
Neat results from algebraic graph theory
Studying algebraic graph theory, I've stumbled across a wide range of results that I found pretty stunning and also useful. I'd like to share them here and ask for your favorite result from this area? …
7
votes
1
answer
821
views
(The) missing Moore graph(s) - uniqueness
In the related literature one often sees the phrase "The missing Moore graph" which (to me) tacitly implies that the missing Moore graph (if exists) is unique.
Is there a result of this type or is or …
- 3,463