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 10035
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.
0
votes
1
answer
78
views
Counting and constructing some special planar graphs
We look for the property that a graph is both planar and has a trivial automorphism group.
How many non-isomorphic $n$-vertex graphs have such property and is there an $O(n^\beta)$ (at least randomiz …
- 13.9k
-1
votes
1
answer
34
views
Graph with small automorphism and large isomorphism
Is there a graph family on $n$-vertices such that any graph $G$ in the family have small automorphism group (say $|Aut(G)|\leq n^c$ for some fixed $c>0$) which if $G$ and $H$ are isomorphic then the s …
- 13.9k
0
votes
1
answer
88
views
Graphs with prescribed Automorphism groups [closed]
For every $k\in\Bbb N$ is it possible to find a graph $G$ on large enough $n\in\Bbb N$ vertices such that $\big|Aut(G)\big|=(n-k)!$? Is it possible to construct it quickly?
- 13.9k
1
vote
1
answer
134
views
On homomorphisms between vertex transitive graphs
In general there is no relation between automorphism groups of subgraphs and the main graph. However, this question is about vertex transitive graphs.
Given vertex transitive $G$ and $H$ such that $| …
- 13.9k
1
vote
0
answers
186
views
Grothendieck Constant of a graph and approximation limits
Let $K(G)$ be the Grothendieck constant of a graph with adjacency matrix $A$. How is $K(G)$ precisely related to approximation limits for some standard NP complete problems such as Chromatic, Independ …
- 13.9k
3
votes
1
answer
245
views
graph homomorphism
Let $G$ and $H$ be two non-bipartite graphs. We know that, if $\exists$ homomorphism $\phi : G \rightarrow H$, then $\omega(G) \le \omega(H)$ where $\omega$ is clique number.
$(1)$ Does the converse …
- 13.9k
2
votes
1
answer
251
views
Factors of Kneser graph
With respect to the Strong product, is the Kneser graph prime and if not how does one find a prime decomposition? Are there any references or algorithms?
- 13.9k
2
votes
2
answers
106
views
Minimal edge color on constraints
Is minimum colors needed to assign colors to edges of complete graph $K_n$ so that every even simple cycle contains an odd number ($>1$) of colors much larger than $(\log n)^\beta$ or $n^{\frac{1}\bet …
- 13.9k
2
votes
0
answers
72
views
How effective is using local property to test Shannon capacity?
A key tool in graph theory is the laplacian which is a local property. We can form a semidefinite programming and get an upper bound for Shannon capacity using laplacian.
Shannon capacity is inherent …
- 13.9k
6
votes
2
answers
359
views
Who first used/gave a coordinate representation of a graph?
In his proof of the Shannon capacity of a graph, Lovasz utilizes a coordinate representation of the pentagon (namely an orthonormal representation). Who first utilized a coordinate representation for …
- 13.9k
0
votes
3
answers
376
views
On independent sets of graph
Given $G$ a regular graph on $n$ vertices, denote $\alpha(G)>1$ to be independence number.
Denote $\Gamma(G)$ to be collection of possible subset of independent vertices in $G$ of cardinality $\alpha …
- 13.9k
3
votes
1
answer
184
views
Capacity of Cycle Graphs
Shannon capacity $\Theta(G)$ of pentagon is achieved at $2$-fold strong product of the pentagon.
It is also known that the Lov\'asz theta $\vartheta(G)^m\neq\alpha(G^{\boxtimes m})$ for any finite po …
- 13.9k
2
votes
1
answer
255
views
Bipartite graphs with prescribed Matching $M$ and genus $g$.
Let $B_{n,n}$ be a bipartite graph on $2n$ vertices with $n$ vertices of each color.
Given two integers $g$ and $M$, construct the smallest genus $g$ $B_{n,n}$ with exactly $M$ matchings.
My first …
- 13.9k
3
votes
1
answer
162
views
Quick tests for Self complementary vertex transitive graphs
Are there any quick tests to determine if a graph is Self complementary vertex transitive? That is if the graph is self complementary vertex transitive the answer should be yes.
- 13.9k
9
votes
1
answer
1k
views
Lovasz theta function and independence number of product of simple odd-cycles
Lovasz theta function $\vartheta(G)$ of a graph $G$ provides an upper bound for the independence number of a graph, $\alpha(G)$ and $\Theta(G) = \lim_{k\rightarrow \infty}\sqrt[k]{\alpha(G^{k})}$. Tha …
- 13.9k