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 19885
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.
3
votes
Accepted
Maximum and minimum diameter of categorical graph product
As Prof. Royle said, there is such upper bound which happen in many times. But, there is a good paper which this diameter exactly determined and maybe it is useful for you.
The paper is: "On the diam …
- 4,784
5
votes
0
answers
139
views
Existence of a class of graphs with a special property
In the following, suppose all graphs are simple and finite. For a given graph $G$, we denote its complement by $\overline{G}$. Let $*$ be a binary operation on graphs, such as Cartesian product, Krone …
- 4,784
8
votes
Tutte's conjecture on Petersen graphs
Theorem 10.21 (see page 268) of the book "Chromatic Graph Theory" (which is written by Gary Chartrand and Ping Zhang), confirm that this conjecture is proved and in $2001$, Robertson, Saunders, Seymou …
- 4,784
7
votes
Accepted
How many triangles can a connected graph with $n$ vertices and $m$ edges have?
It is a bound and since it is very long, I wrote it an answer, may be it can be helpful.
Let $G$ be a connected graph with $n$ vertices and $m$ edges. Suppose the eigenvalues of this graph are $\lamb …
- 4,784
4
votes
Accepted
diameter of Cayley graphs
Suppose $G$ is a finite group and we choose $S'=G\setminus\{1,a,a^{-1}\}$. Then if we let $S=S'\cup \{a,a^{-1}\}$, the diameter of the cayley graph $Cay(G,S)$ is one, but the diameter of the Cayley gr …
- 4,784
5
votes
Existence of special graph
I think you mean the adjacency spectrum of simple graph. Since the eigenvalues of graphs are algebraic integers, so the answer to your question is no. For example, the number $\frac{226}{17}$, which i …
- 4,784
4
votes
0
answers
85
views
Determined labels and reconstruction conjecture
In the reconstruction conjecture $(RC)$, if we know the $k$, $0\leq k \leq n$ labels of the vertices, then $RC$ is true.
Do we know the minimum $k$ that the above statement is true?
Do we have any res …
- 4,784
0
votes
Examples of graph properties characterized by forbidden (not necessarily induced) subgraphs
There are some results about $P_n$-free graphs. For example;
A graph $G$ is $P_4$-free if and only if each connected induced subgraph of $G$ contains a dominating induced $C_4$ or a dominating vertex …
- 4,784
3
votes
Non-DS circulant graphs
We know that all groups with prime order is CI-group. So, if two circulant graph with $p$ vertices be cospectral, then they are isomorphic. So, as Dear Brendan said, the answer is no.
But about your …
- 4,784
4
votes
Accepted
normalized laplacian spectrum of trees
It is a partial answer for your question:
For $P_n$, the form of normalized laplacian matrix is three diagonal and with some calculations, we can show that all its normalized laplacian eigenvalues ar …
- 4,784
2
votes
Reflexive (hyperbolic) graphs
I think this question is so hard, since we do not have any control on other eigenvalues, specially on the minimum of them.
As an evidence (and maybe useful for your work), recently S. M. Cioab$\br …
- 4,784
1
vote
Properties of Graphs with an eigenvalue of -1 (adjacency matrix)?
There are a lot of graphs with this property. I just introduce two classes that are very famous:
The Friendship graph $F_n$ that is $K_1\nabla nK_2$, where $\nabla$ means the join of two graphs. Thes …
- 4,784
3
votes
1
answer
199
views
Estimation of DS graph growth
We know that $DS$ graphs are such connected graphs that determinable by their adjacency spectrum.
Suppose $DS(n)$ and $G(n)$ show the number of $DS$ graphs and all graphs with $n$ vertices,respective …
- 4,784
2
votes
0
answers
110
views
Mutual benefits of coding theory and the reconstruction conjecture
Let $G_n$ denotes all graphs with $n$ nodes. For any graph $G$ in $G_n$, the adjacency matrix $A(G)$ can be viewed as a codeword of length $n^2$. Also, the codes arises from $G_n$ is a linear binary c …
- 4,784
3
votes
Accepted
Largest girth of a graph of average degree k
You can find your answer in the paper:
Generalized Girth Problems in Graphs and Hypergraphs
By Uriel Feige and Tal Wagner.
Let $A_2(n,k)$ denotes the optimal upper bound for girth of graphs with $n$ n …
- 4,784