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 answers only
not deleted
user 108556
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.
10
votes
Accepted
Graph automorphism group
Here is a complete answer.
The answer to Q1 is 'no, because $A_w=\{1,2\}$ and $A_s=\{1\}$'.
The answer to Q2 is 'no, $A_w$ contains merely two, while $A_s$ contains merely one element.
The answer to …
- 6,051
2
votes
Accepted
Strong and weak chromatic number of infinite hypergraphs of finite rank
Since the OP did not require that the rank of the hypergraph be bounded, the answer to the question is 'obviously yes'. An example is any hypergraph $H$ which is(*) the
disjoint union of $\aleph …
- 6,051
1
vote
Counting Problems where Labeled is Known but Unlabeled is Not
Since the question
I am hoping to solicit examples of other counting problems of this type, particularly ones where the labeled count is known exactly but little is known about the unlabeled count.
…
CommunityBot
- 1
16
votes
Does there exist a graph with maximum degree 8, chromatic number 8, clique number 6?
Relevant footnotes to Fedor Petrov's nice, helpful, and completely correct answer.
Fedor's answer seems essentially unimprovable both in brevity and completeness (it's all there).
I hadn't expected …
- 6,051
5
votes
Neighborhood fingerprint of a graph
Answer. Arguably the simplest infinite set of counterexamples to "Does the converse hold?" are provided by the Möbius ladder's vis-à-vis the prism graphs. Any pair of such graphs (of equal orders) bea …
- 6,051
3
votes
Accepted
In the context of directed graphs is it standard notation to allow an element of an independ...
Well, I personally don't think there is much to say here; regarding "are there any authors who define independent vertex-sets in directed graphs where vertices contained in loops are permitted": I kno …
- 6,051
1
vote
How to characterize "matching-transitive" regular graphs?
The following answers the question of Katja Berčič at in the comment at 2018-03-16 16:48:59Z: "is there a non $K_{2n}$, non $K_{n,n}$ example of a matching transitive graph of degree at least 3?"
Pro …
CommunityBot
- 1
2
votes
How many $40$-vertex cubic bipartite graphs have determinant $\pm 3$?
A relevant comment, which the comment boxes cannot conveniently contain.
Summary. Briefly, the comment below gives, thanks to basic linear algebra and an easy theorem of Harary, a reformulation of you …
CommunityBot
- 1
7
votes
Accepted
Does there exist a nonsingular graph for which the determinant of its adjacency matrix remai...
Proposition. The unique smallest graph w.r.t. number of edges of the requested kind is
. (This graph is isomorphic to graph no. 126 below).
It has $6$ vertices and $8$ edges.
The determinant o …
- 6,051
7
votes
Where on the internet I can find a database of graphs?
Discrete ZOO should also be mentioned here. As of 2 March 2018, it reports to host 212238 graphs.
- 6,051
2
votes
Accepted
Is the difference sequence of the maximum size of $k$-colorable subgraph non-increasing?
Answer. No, this sequence will not always be non-increasing. A counterexample is given in
[AB1980] Michael O. Albertson, David M. Berman, The Chromatic Difference Sequence of a Graph, Journal of …
- 6,051
4
votes
Accepted
What does the basis of the null space of the constraint matrix of a flow problem look like?
An illustrated example right-away
Not to immediately bore you with lengthy preliminary remarks, let me begin with an illustration which, in a sense, already is an answer in itself. Here is an example …
- 6,051
1
vote
Importance of the $2^{\tau(G)}\leqslant A(n,g(G))$ conjecture
Permit me to make a relevant (though inconclusive) observation regarding your question "Does the fact that G should be directed matter?", an observation which lends some intuitive credibility to 'your …
- 6,051
4
votes
Accepted
"Eccentricity" in the Definition of Graph Center
Re: 'is it customary'. Yes, this is the customary term, and I don't know any reasonable alternative to using the eccentricity function. The term (with exactly this definition) already occurs on page 3 …
CommunityBot
- 1
6
votes
Accepted
Measurable maximal independent set in infinite graph of bounded degree
A relevant statement is Proposition 4.2. in
[KST1999] A. S. Kechris, S. Solecki, S. Todorcevic, Borel Chromatic Numbers. Advances in Mathematics 141, 1-44 (1999)
In short, the proposition shows that …
CommunityBot
- 1