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 60732
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.
16
votes
4
answers
1k
views
A labelling of the vertices of the Petersen graph with integers
The vertices of the Petersen graph (or any other simple graph) can be labelled in infinitely many ways with positive integers so that two vertices are joined by an edge if, and only if, the correspond …
- 3,707
11
votes
1
answer
865
views
Is the divisibility graph of the proper divisors of n more often planar than not?
Define the divisibility graph of a set of positive integers as the graph whose vertices are the integers, two of which are joined by an edge if one divides the other.
For all N, is it true that intege …
- 3,707
9
votes
1
answer
250
views
Finding the largest number which cannot be the sum of the labels of the Petersen graph
The vertices of the Petersen graph (or any other simple graph) can be labelled in infinitely many ways with positive integers so that two vertices are joined by an edge if, and only if, the correspond …
- 3,707
9
votes
3
answers
468
views
The diameter of a certain graph on the positive integers
Let $G(n)$ be the graph whose vertices are the positive integers $1,2,3,4, \ldots, n$ two of which are joined by an edge if their sum is a square. Is the diameter of this graph 4 for all sufficiently …
- 3,707
6
votes
6
answers
1k
views
Least number of vertices in a graph with which one can uniquely recover some partition of N
Given a partition of an integer $N$, its $P$-graph is the graph whose vertices are its parts, two of which are joined by an edge if and only if they have a common divisor greater than one (i.e. they a …
- 3,707
6
votes
1
answer
413
views
Ramsey's number R(4,4) with arithmetic progressions
Can 17 positive integers in arithmetic progression be found such that that no four of them have, pairwise, a common divisor greater than 1, but, likewise, no four of them are, pairwise, relatively pri …
- 3,707
4
votes
0
answers
229
views
A property of the partitions of 311 with regard to the divisors of its parts
Given a multiset of positive integers, its P-graph is the loopless graph whose vertex set consists of those integers, any two of which are joined by an edge if they have a common divisor greater than …
- 3,707
4
votes
Least number of vertices in a graph with which one can uniquely recover some partition of N
Freddy Barrera has shown that $k(1000)>5$ by verifying that every graph with fewer than 6 vertices (other than the singleton) is the P-graph of at least two partitions of 1000. On the other hand, from …
- 3,707
2
votes
1
answer
174
views
Graceful graphs all of whose vertices are labelled with primes or squares
Do graceful graphs exist with more than any arbitrarily large number of vertices, all of which are labelled with a prime or non-negative square number.
Recall that a graceful graph is a graph with m …
- 3,707
2
votes
0
answers
229
views
Generating all graphs of order 4 with the help of Collatz
Given a set of positive integers, its common divisor graph ( CD-graph) is the graph whose vertices are the integers, two of which are joined by an edge if (and only if) they have a common divisor grea …
- 3,707
2
votes
1
answer
212
views
Are there graphs for which infinitely many numbers cannot be the sum of the labels of its ve...
The vertices of any simple graph can be labeled in infinitely many ways with positive integers so that two vertices are joined by an edge if, and only if, they have a common divisor greater than 1.
…
- 3,707
1
vote
1
answer
187
views
Counting tournaments with ties
An improper tournament, or tournament with ties, is a graph in which every pair of nodes is connected by a single uniquely directed edge or by a single undirected edge.
There are 1, 2, and 7 improper …
- 3,707
1
vote
Least number of vertices in a graph with which one can uniquely recover some partition of N
For the sake of completeness, here is the graph found by user44191 (see above), which shows that $k(1000)<11$:
- 3,707
1
vote
Least number of vertices in a graph with which one can uniquely recover some partition of N
@user44191 Based on your "cycles and tails" idea Freddy Barrera devised and checked by exhaustive computer search that from the following P-graph a unique partition of 1000 in nine parts can be recove …
- 3,707
0
votes
2
answers
617
views
Graphs determined by sets of consecutive integers
Given a set of positive integers, its P-graph is the graph whose vertex set consists of those integers, two of which are joined by an edge if they have a common divisor greater than 1, that is, they a …
- 3,707