The study of maximal or minimal graphs satisfying certain properties.

learn more… | top users | synonyms

1
vote
0answers
22 views

Prove the equivalence of Szemeredi’s regularity lemma

In my textbook, Szemeredi’s regularity lemma states as $\forall\epsilon>0,\forall$ integer $m$ $\exists$ integer $M$ $\forall$ graph $G$ on $n\ge m$ vertices $\exists k$ with $m\le k\le M$ and an ...
-1
votes
0answers
13 views

Finding and classifying extremal points of a function with 2 variables

Hi I was just wondering if anyone could give an example of how to find and classify extremal points of a function with 2 variables I've been trying to find one and can't find it anywhere. Thanks in ...
1
vote
0answers
114 views

$(r+1)$ Clique of Induced subgraph and Turan’s theorem

$G$ is a $s$ regular graph. $A$ is a set of vertices where $|A| = s$ and $A \subseteq G$. $E$ is the number of edges of $G$. $n$ is the total number of vertices of $G$. Problem: Find the lower ...
0
votes
0answers
38 views

Deleting tree from graph with large average degree will raise chromatic number

I am trying to bite problem 7.17 in Diestel graph theory book: 7.17 Can large average degree force the chromatic number up if we exclude some tree as an induced subgraph? The hint is: Consider ...
4
votes
1answer
87 views

Minimum number of edges such that $\chi_1=\chi$

Given a graph $G(V,E)$, let $\chi(G)$ be its chromatic number, and $\chi_1(G)$ its 1-improper chromatic number (meaning that each node can have at most 1 neighbor with the same color; or another way ...
1
vote
1answer
30 views

By adding $k$ edges to a $K_r$-free graph, what is the maximum clique number attainable?

Denote by $\omega(G)$ the size of a maximum clique of a graph $G$. Suppose $G$ is a $K_r$-free graph (i.e. $\omega(G) < r$), and let $G'$ be a graph obtained by adding at most $k$ edges to $G$. ...
1
vote
0answers
29 views

Good embeddings for degree-diameter graphs

I've put together a degree-diameter notebook for various graphs of the degree diameter problem. My favorite table is at The (Degree,Diameter) Problem for Graphs. Here are sample edge lists without ...
0
votes
2answers
29 views

To find a extremal point of a function with parameters

I have a function $$f(x) = (x-5m)(x+m)^2$$ I have tried to find the extremal points of this function (and then find if it's local maxima or minima). That means I need to find the x of derivative. The ...
2
votes
0answers
37 views

Turan's theorem for balanced r-partite graphs

I'm curious about the following restricted version of Turan's theorem: Among all $r$-partite graphs that are balanced (exactly $n/r$ nodes per part), what is the maximum size of a graph with no ...
2
votes
1answer
30 views

On bounding the diameter of a undirected simple connected graph

This may be a something already there in literature but I am unable find it: Given an undirected simple connected graph $G$ whose vertices has a degree at-least $d$ and $\ge c n^2 $ edges, where $0 ...
1
vote
2answers
214 views

How do you find the value of n in this example

$$n^{n-2} = 16$$ I know $n = 4$ through trial and error but how do you find $n$ in a conventional manner? I'm basically trying to solve how many nodes are in a tree that has $16$ spanning trees ...
0
votes
1answer
35 views

Can a chord determine two fundamental circuits in a graph

I was studying fundamental circuits,fundamental cutsets related theorems,then I came across a question in my mind: Is it possible that a chord with respect to a given spanning tree in a graph ...
0
votes
0answers
31 views

Induction of maximum degree in multigraph

The Caen and Furedi paper The maximum size of 3-uniform hypergraphs not containing a Fano plane states several times and we can finish by induction and I can't work out how. Specifically in the ...
0
votes
1answer
16 views

Why does $K_{\chi(H)}(|H|)$ contain the graph H?

Why does $K_{\chi(H)}(|H|)$ necessarily contain the graph H? This is part of the more general question as to why $K_{\chi(H)}(t)$ should contain H for sufficiently large t. Here $K_{r}(t)$ is a ...
0
votes
0answers
27 views

Determine the value of $ex(n,P_4)$

I want to determine the exact value of $ex(n,P_4)$ I believe that the answer to this is $n$, if $n\equiv 0$ (mod $3$), and $n-1$ otherwise. Given n vertices, one can create multiples of $K_3$. If ...
2
votes
2answers
218 views

Deriving the number of edges in a Turán graph

When stating Turán's theorem, the Turán graphs are often used to give an upper bound on the possible number of edges in a graph without a clique of a certain size. This bound can also be proven ...
0
votes
0answers
43 views

Why functions derivitive crosses x axis, where function does not have an extreme point?

My function: $(x+0.4)^2-\cos\left(1+\frac{\cos(x/2)}{\sin(x/2)}\right)$ My derived function: $0.8+2x+\frac{1}{2}\frac{1}{\sin(x/2)^2}\sin\left(1+\frac{\cos(x/2)}{\sin(x/2)}\right)$ Where $x$ is very ...
0
votes
0answers
9 views

Family of graphs with structural intersection (namely, no isolated vertices)

In the book Extremal Combinatorics: With Applications in Computer Science I found the following theorem: Theorem. Suppose that $\mathcal{F}$ is a family of (labeled) subgraphs of $K_n$ such that for ...
0
votes
2answers
36 views

About Proof by extremality

Can someone explain the basic idea behind proof by extremality in simple language? Like in proof by contradiction, for $P \rightarrow Q$, we assume $P$ and not $Q$ and show they cannot happen ...
1
vote
1answer
142 views

Turan's theorem - maximum number of edges.

Question: 30 people need to place a call to each other using their cellular phones (one call per each pair). A cellular phone company gets 1 $ for each call between two people at distance between 800 ...
0
votes
1answer
71 views

Graph theory and tree company

I appreciate anyone who answer this question and I anyone who design appropriate graph.
5
votes
1answer
154 views

Every simple planar graph with $\delta\geq 3$ has an adjacent pair with $deg(u)+deg(v)\leq 13$

Claim: Every simple planar graph with minimum degree at least three has an edge $uv$ such that $deg(u) + deg(v)\leq 13$. Furthermore, there exists an example showing that 13 cannot be replaced by ...
1
vote
1answer
36 views

Do complete graphs maximize the number of triangles?

Let $G$ be a graph with $a\choose 2$ edges (and an arbitrary number of vertices). Is it true that it has at most $a\choose 3$ triangles? Context: this continues the question Number of triangles in a ...
2
votes
2answers
63 views

Graph containing every trees of size $n$ as subgraphs

What is the minimum number of edges of graph $G$, so that every tree of size $n$ is a subgraph of $G$? I personally managed to find a lower bound of $c n \log n $ and an upper bound of $C n \log ...
3
votes
1answer
132 views

Definition of compatible vertices

I'm reading the Extremal Graph Theory book by Bollobás, and I'm stuck at the definition of 'compatible vertices'. It's here at the bottom of p.13 It says : "Call two vertices compatible if every ...
1
vote
0answers
33 views

A inequality on a graph and finding the best constant

Find the smallest positive constant $c$ satisfying: For any simple graph $G=G(V,E)$, if $|E|\geq c|V|$, then $G$ contains $2$ cycles with no common vertex, and one of them contains a chord. Note: The ...