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 171032
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
1
answer
798
views
For a three-connected graph, is there a contraction edge that strictly increases vertex conn...
In graph theory, an edge contraction is an operation which removes an edge from a graph while simultaneously merging the two vertices that it previously joined. edge contraction
As defined below, an e …
- 1,851
0
votes
1
answer
198
views
Is graph's planar embedding unique if each block of one planar graph is 3-connected?
A planar graph is one which has a plane embedding. Two drawings are topologically isomorphic if one can be continuously deformed into the other. If we wrap a drawing onto a sphere, and then off again, …
- 1,851
1
vote
0
answers
77
views
Is there any theorem similar to the Tutte–Berge formula?
Tutte–Berge formula is a characterization of the size of a maximum matching in a graph.
The theorem states that the size of a maximum matching of a graph
${\displaystyle G=(V,E)}$ equals $${\displays …
- 1,851
0
votes
0
answers
70
views
A counterexample of a theorem about matching extendable
$M$ is perfect if $M$ covers all vertices of $G$, and $M$ is extendable if $G$ has a perfect matching containing $M$. Moreover, a graph $G$ with at least $2k + 2$ vertices is said to be $k$-extendable …
- 1,851
1
vote
1
answer
95
views
Is there a monograph or review of Hamiltonian cycles of graphs (or long cycles of graphs)？
In graph theory, a Hamiltonian cycle is a cycle that visits each vertex exactly once. Hamiltonian cycle has a long history, and I have followed some articles.
We can find plenty of examples of Hamil …
- 1,851
1
vote
0
answers
162
views
Is there a characterization for graphs with independence number two?
An independent set is a set of vertices in a graph, no two of which are adjacent. A maximum independent set is an independent set of the largest possible size for a given graph. The size of a maximum …
- 1,851
4
votes
1
answer
222
views
Sizes of triangle-free graphs with independence number $k$
A triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. The independence number $α = α(G)$ of a graph $G$ is the cardinality of a maximum in dependent set of …
- 1,851
0
votes
0
answers
76
views
Graphs where any cycles are adjacent
Graphs with minimum degree three that any two cycles have common vertex, have been characterized by Lovász. I see this result from the Plumer article （On the cyclic connectivity of planar graphs (197 …
- 1,851
1
vote
1
answer
287
views
Abnormal toroidal drawing of graph
1. Some background knowledge
Definition. A torus, informally, is the doughnut-shaped surface that we get by taking a square made out of some arbitrarily-stretchy material and gluing together opposite …
- 1,851
4
votes
1
answer
202
views
Can't lower bound be improved on number of light edges in planar graph with minimum degree f...
Let an $i$-vertex be a vertex of degree $i$. Let an $i, j-$ edge be an edge joining an $i-$vertex to
a $j-$vertex. Given a plane graph G, let $e_{i,j}$ be the number of $i, j-$edges of $G$.
I found Bo …
- 1,851
0
votes
Accepted
Is graph's planar embedding unique if each block of one planar graph is 3-connected?
Thanks for Brendan McKay's help. The following two are indeed not same embedding. When the subgraph on the right is reversed to the 3 face of the graph on the left subgraph.
- 1,851
3
votes
1
answer
146
views
Constructing a 1-planar graph that has no rectilinear drawing
A 1-planar graph is a graph that can be drawn in the Euclidean plane in such a way that each edge has at most one crossing point, where it crosses a single additional edge.
1 planar graph
I read the f …
- 1,851
1
vote
1
answer
278
views
Confused about the definition of convex drawing of plane graph
When I looked up the definition of convex drawing of planar graph, my confusion mainly focused on the outer face.
The following definition of convex drawing is from Wikipedia.
In graph drawing, a co …
- 1,851
4
votes
0
answers
121
views
Find a good drawing for the edges of any two component of $G-S$ that do not cross
A drawing of a graph $G$ on the plane $P$ is a representation of $G$, where vertices are distinct points in $P$, and edges are Jordan arcs in the plane joining the points corresponding to their end ve …
- 1,851
0
votes
0
answers
222
views
I don’t understand the two ISOMORPHISM embedding definitions of planar graph in plantri soft...
The plantri (see http://users.cecs.anu.edu.au/~bdm/plantri/) is a program that generates certain types of graphs that are
imbedded on the sphere. Exactly one member of each isomorphism class is output …
- 1,851