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 43266
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.
4
votes
Accepted
Adding vertex-disjoint edges to reduce the diameter
Yes. Let $G=(V,E)=P_k$, the $k$-point path, where $k=3\cdot2^{n-1}-1$, and let $F$ be any vertex-disjoint extension of $E$; I claim that the graph $H=(V,F)$ has radius $\operatorname{rad}(H)\ge n$.
A …
- 13.4k
4
votes
Accepted
A question about independent set in regular graphs
Clearly, if $G$ is $1$-regular or $2$-regular, and if $T$ is an independent set in $G$, then there is a maximal independent set $H$ in $G$ such that $T\cap H=\emptyset$.
Let $G$ be the $3$-regular gr …
- 13.4k
4
votes
Accepted
Diameter of undirected, connected, vertex-transitive graph on $n$ vertices
The answer to the second question is yes. A vertex-transitive connected finite graph (with more than two vertices) is $2$-connected, i.e., it can't be disconnected by removing a vertex. In a $2$-conne …
- 13.4k
1
vote
Accepted
Domination numbers of infinite graphs
I think I have a counterexample. I will construct the complement of the graph $G$ as the union of an infinite sequence of finite graphs $H_n.$
Let $H_0$ be a graph with three vertices and no edges.
…
- 13.4k
4
votes
How many vertices can a self-complementary graph have?
Quoting an answer I posted some time ago on MathSE:
Take a complete graph with vertex set $V$ and edge set $E={V\choose2}$. Let $\alpha$ be any permutation of $V$ in which the length of each cycle …
- 13.4k
3
votes
Minimal and maximal degrees in self-complementary graph
This is really just a comment on Brendan McKay's answer, but I'd like to point out that there are also infinite self-complementary graphs with minimum degree $\delta=1$. Here are two different ways to …
- 13.4k
1
vote
Connected vs strongly connected graphs
Trivially:
A digraph $D$ is strongly connected if and only if it satisfies the two conditions:
(i) the underlying graph of $D$ is connected;
(ii) every arc in $D$ is part of a directed cycle.
If a fin …
- 13.4k
2
votes
Accepted
Hadwiger partitions where one block is always a singleton
The graph $G=2K_n$ is a counterexample. Or, if $G$ is supposed to be connected, then $G=2K_n+e\ $ (that's $2K_n$ with an additional edge) is a counterexample for $n\ge3.$
- 13.4k
2
votes
Accepted
Coloring graph such that the coloring classes are not maximal independent sets
Of course not. Consider any graph $G$ and any coloring map $\chi:G\to\kappa_0$. Choose $\beta\in\kappa_0$, extend the independent set $\chi^{-1}(\beta)$ to a maximal independent set $S$, and define a …
- 13.4k
8
votes
Accepted
Graph automorphism that swaps two pairs of nodes
Label the vertices of $C_5$ cyclically: $x,y,z,w,v$. There is a (unique) automorphism that swaps $x$ and $y$, and another (unique) automorphism that swaps $z$ and $w$, but there is no automorphism tha …
- 13.4k
4
votes
Accepted
Non-chromatic paths in Hamiltonian graphs
Counterexample. Let $G$ be the graph with vertices $v_1,v_2,v_3,v_4,v_5,v_6$ and edges $v_1v_2,v_2v_3,v_3v_4,v_4v_5,v_5v_6,v_6v_1,v_1v_5,v_4v_6.$
The graph $G$ is Hamiltonian, since $v_1,v_2,v_3,v_4, …
- 13.4k
2
votes
Accepted
Is the set of edge of a cubic graph the union of a cycle and and an Acyclic graph?
Let $G$ be the cubic graph on $30$ vertices obtained by replacing each vertex of the Petersen graph with a triangle. Then $G$ is $3$-connected because the Petersen graph is $3$-connected, and there is …
- 13.4k
3
votes
Hedetniemi for pseudo-chromatic number $\psi(G)$
Here is a very simple example for $\psi(G\times H)\gt\max\{\psi(G),\psi(H)\}$.
The graph $G=H=K_3$ has achromatic number and pseudo-chromatic number equal to $3$. The tensor product $K_3\times K_3$ ha …
- 13.4k
5
votes
Accepted
Embedding any graph into a vertex-transitive graph of the same chromatic number
For $k\in\mathbb N$ the random $k$-chromatic countably infinite graph is vertex transitive and contains an isomorphic copy of every $k$-colorable countable graph as an induced subgraph. I suppose this …
- 13.4k
1
vote
Accepted
Decreasing the chromatic number by $2$ by removing $2$ well-chosen vertices
Let $G_0=(V_0,E_0)$ be a complete graph of order $n\ge4$. Choose two distinct points $a,b\in V_0$ and two distinct points $x,y\notin V_0$. The graph $G=(V,E)$ with vertex set $V=V_0\cup\{x,y\}$ and ed …
- 13.4k