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 19075
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.
8
votes
2
answers
1k
views
A flag complex is contractible iff the underlying graph is....?
Let $G$ be a finite simple graph and let $C(G)$ be the flag complex associated to $G$ (the set of vertices of $C(G)$ is the vertex set of $G$ and the set of all cliques of $G$ are its simplexes).
Ar …
- 3,738
5
votes
2
answers
863
views
Can the friendship graph be determind by its adjacency spectrum?
Let $n\geq 1$ be an integer. The Friendship Graph (or Dutch windmill graph or $n$-Fan) $F_n$ is a graph that can be constructed by coalescence $n$ copies of the cycle graph $C_3$ with a common vertex. …
- 3,738
4
votes
Can the friendship graph be determind by its adjacency spectrum?
This is answered in the following recent paper:
The graphs with all but two eigenvalues equal to ±1
By Sebastian M. Cioabă, Willem H. Haemers, Jason Vermette, Wiseley Wong
One may download it from
…
- 3,738
3
votes
1
answer
640
views
Strongly regular graphs with the same parameters as Paley graph
It is known that the Paley graph $P(q)$ for $q = 5, 9, 13$ or $17$ vertices are the only strongly regular graph with the parameters as $P(q)$.
If $q \geq 25$, is the following assertion true:
The …
- 3,738
3
votes
0
answers
230
views
Computing the Edge Chromatic Polynomial of a graph
Is there a recursive formulae to compute the edge chromatic polynomial of a graph?
The following formulae is known for the vertex chromatic polynomial of a grapg $G$
$P(G,x)=P(G-uv, x)- P(G/uv,x)$ …
- 3,738
2
votes
0
answers
160
views
Perfect P6-free graphs with further properties
Let $G$ be a graph without any hole or antihole of odd length at least 5 (i.e. $G$ is a Berge graph and so by the Strong Perfect Graph Theorem, $G$ is perfect).
Assume further that $G$ has no antihol …
- 3,738
2
votes
1
answer
376
views
Godsil-Mckay switching applied on the Paley graph
It is well-known that the Paley graph $P(q)$ is a strongly regular graph with parameters
$(4t+1,2t,t-1,t)$. Suppose that $v$ is a vertex in the Paley graph $P(q)$. Suppoe that $C$ is the set of all …
- 3,738
2
votes
Why do we associate a graph to a ring?
The Fischer graph is one of examples; see page 569 of
Suzuki, Michio. Group theory. II. Translated from the Japanese. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathemati …
2
votes
1
answer
127
views
Eigenvalues of a graph and its one-edge-delation graph
Let $G$ be any graph with at least one edge and let $e$ be any edge of $G$. Let $G-e$ denote the subgraph of $G$ obtained by deletion of the edge $e$. Assume that $G$ has $n$ vertices.
Suppose …
- 3,738
1
vote
2
answers
196
views
Clique number of a regular graph with respect to that of a certain edge decomposition
Let $G$ be a regular graph having spanning regular subgraphs $G_1,\dots, G_k$
whose edge sets are disjoint and their union is the whole edge set of $G$.
Is it true that the clique number of $G$ is bou …
- 3,738