Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

learn more… | top users | synonyms

0
votes
0answers
7 views

Hill climbing and K-most influential person problem

In graph theory and select top K-most influential person problem, Hill climbing algorithm get 63% of optimal solution. Can give me an example(graph) that Hill climbing can't find global optimum in ...
0
votes
0answers
11 views

Property of simple bipartite graphs

I'm trying to solve the following exercise from the book A Textbook of Graph Theory by R. Balakrishnan and K. Ranganathan Show that for a simple bipartite graph, $m\leq \frac{n^2}{4}$ $m$ is the ...
0
votes
1answer
15 views

Minimum Spanning Trees Weight Question

Given any undirected connected graph. If we redefine the weight of a spanning tree to the maximum weight of an edge (if the largest weight is 10 the weight of the tree is 10) are there any cases where ...
-3
votes
0answers
12 views

Circuits and cutsets in graphs

Prove that, if two distinct circuits of a graph G each contain an edge e, then G has a circuit which does not contain e. Prove a similar result with 'circuit' replaced throughout by 'cutset'.
0
votes
1answer
20 views

Looking for algorithms capable of modifying graph structure

I realize this is a quite a general request. I'm just looking for examples of path searching algorithms for directed graphs which are capable of utilizing simple modifications (adding vertices, adding ...
3
votes
1answer
44 views

Traveling salesman problem: why visit each city only once?

According to wikipedia, the Traveling Salesman Problem (TSP) is: Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city ...
0
votes
0answers
15 views

Regular epimorphisms in the category of simple, undirected graphs

Let $\textbf{Grph}$ be the category whose objects are graphs $G = (V,E)$ such that $V$ is a set and $E \subseteq \mathcal{P}_2(V) := \{\{a,b\} \subseteq V: a\neq b\}$. We sometimes write $E(G)$ for ...
0
votes
1answer
34 views

Number of vertices in a hexagon graph?

What formula would find the number of vertices within a 'normal' hexagonal graph, based on its radius (number of hexagons from center to edge)? I've figured with pseudo code: ...
0
votes
0answers
4 views

Vertex invariants based on finding minimal combined shortest paths

A possible vertex invariant for a vertex v is v's smallest n-neighbourhood consisting of the induced subgraph rooted in v of all vertices n edges away from v. Question 1: I'm wondering if this ...
0
votes
0answers
8 views

Examples of Algorithms capable of modifying graph structure?

I'm currently working on a problem where one is presented with 2 connected digraphs (call them G1 and G2), each with an associated set of logical constraints. Each vertex of each graph represents a ...
1
vote
0answers
20 views

Graph Theory-forest and its components

Let G be a forest with two components and at least four vertices. Is it true that G has at least four leaves? the graph is which is I mentioned you
-3
votes
1answer
24 views

Graph Theory-maximal path [on hold]

Can anyone please draw this, I have been trying to draw for a long time
-4
votes
1answer
33 views

Graph theory -tree [on hold]

Question 3. Prove or give a counter example: A graph $G$ with exactly one vertex of degree one contains a cycle.
0
votes
1answer
19 views

Graph theory-tree

Let $T$ be a tree with exactly two vertices of degree $7$ and exactly $20$ vertices of degree $100$. What is the minimum possible number of vertices in a tree $T$ that satisfies those restrictions?
1
vote
0answers
25 views

Proof that Paley Graphs are strongly regular with parameters $(p,\frac{p-1}{2},\frac{p-5}{4},\frac{p-1}{4})$

A Paley graph is strongly regular with parameters $(p,\frac{p-1}{2},\frac{p-5}{4},\frac{p-1}{4})$. I need to prove that, and obtain the parameters too. Proving it is regular valency $\frac{p-1}{2}$ is ...
0
votes
1answer
18 views

Extending matchings in a bipartite graph

Could I get some help for part b(i) of below please? Thanks. (Part (a) follows from Hall's Marriage Thm, and b(ii) follows quickly from b(i) I think). Let G be a bipartite graph with parts X and Y , ...
1
vote
1answer
21 views

An example of connected graph with vertices having at least 3 degree, but non-hamiltonian?

The question is: Does there exist a simple connected undirected graph $G$ with $7$ vertices with minimal degree $3$ but does not contain any hamiltonian cycle? I've been trying to find an ...
0
votes
1answer
36 views

Counting problem for seating in a circle

I am having a hard time understanding the answer to the following problem from Grimaldi: "At Professor Alfred's science camp, 17 students have lunch together each day at a circular table. They are ...
2
votes
1answer
19 views

Coloring a graph with three colors

Is the statement below correct? A graph which doesn't have a complete graph of order $4$ or more can be colored with $3$ colors, so that no two adjacent vertices have same color. I don't know it is ...
1
vote
0answers
17 views

Adjacency matrix on simple graphs

It is known that one of the eigenvalues in the $k$-regular graph is $k$. I have to prove that for a connected graph with eigenvalue $\Delta$, in which $\Delta$ is the maximum degree in G, the graph ...
0
votes
1answer
13 views

Expected value in graph

You are in a directed weighted graph with $N$ $(63 \le N \le 10^6)$ vertices and $M$ $(1 \le N \le 10^6)$ edges and you want to get from $63^{rd}$ to $4^{th}$ vertex. Going through $i^{th}$ edge takes ...
0
votes
1answer
12 views

Is the transitive closure of a circular graph reflexive?

I feel like it is, but couldn't find anything online to support it - suppose the set A={a,b,c} and the relation set R={(a,b),(b,c),(c,a)}, would the transitive closure be reflexive (ie contain (a,a), ...
-2
votes
1answer
32 views

Suppose there are n suns and n moons Show that every sun can be paid with a moon , with each moon a distance less that 106 miles from the sun. [on hold]

Suppose there are n suns and n moons and every set of moons is within 106 miles from an equal amount of suns. Show that every sun can be paid with a moon , with each moon a distance less that 106 ...
-1
votes
0answers
18 views

Graph Theory - Spanning Trees [on hold]

What is branch in tree? Tree's edge is branch that the subgraph of the tree which is maximal,am I wrong?
2
votes
3answers
60 views

Showing that the complete bipartite graph $K_{a,b}$ is a tree if and only if $a=1$ or $b=1$.

Let $K_{a,b}$ be the complete bipartite graph. Show that $K_{a,b}$ is a tree if and only if $a = 1$ or $b = 1$. The way my professor showed us for a complete graph is as below. I just don't know how ...
1
vote
0answers
23 views

Graph Decomposition And Linear Algebra

A module in a graph $G$ is a subset $M$ of the vertices such that all the vertices in $M$ have the same neighbourhoods outside of $M$. That is, if $v_1, v_2 \in M$ and $x \not\in M$, then we have ...
0
votes
1answer
22 views

Graph and language/automaton equivalence

I'm looking for a reference rather than an answer. I think I'm just not Googling the right combination of terms. I imagine that there is a class of graphs which is equivalent to some class of ...
0
votes
2answers
59 views

Minimum number of operations to make all of the strings (objects) the same

Let $A$ be an alphabet, $K$ and $N$ be natural numbers and $X$ be a list of $N$ strings over $A$, each one consisting of $K$ letters. You have one operation ($@f$): convert a string from $X$ to ...
0
votes
1answer
25 views

maxflow-mincut theorem, why no augmenting path implies existence of maxflow

The proof is taken from course Algorithm II, Princeton, coursera. In the proof of iii => i, Why/How iii implies the existence of cut (A, B)?
3
votes
1answer
34 views

Chromatic number $\chi(G)=600$, $P(\chi(G|_S)\leq 200) \leq 2^{-10}$

I am learning martingale and Hoeffding-Azuma inequality recently but do not how to apply the those inequality or theorem here. Let $G=(V,E)$ be a graph with chromatic number 600,i.e. $\chi(G)=600$. ...
3
votes
4answers
299 views

Prove that the graph is connected

I was wondering if someone can help me understand how prove that this graph is connected. Given a graph with n vertices, prove that if the degree of each vertex is at least $(n − 1)/2$ then the graph ...
0
votes
0answers
10 views

Prove $\chi(G) \leq 1 + \max \lbrace \delta(H) : H \text{ is an induced subgraph of } G \rbrace $ [duplicate]

Prove that for every graph G $\chi(G) \leq 1 + \max \lbrace \delta(H) : H \text{ is an induced subgraph of } G \rbrace $ [$\delta(H)$ is the degree of the smallest degree vertex in H]
0
votes
1answer
14 views

Size of outerplanar graph

If $G$ is an outerplanar graph of order $n \geq 2$ and size $m$, show that $m \leq 2n -3$ [I can show the result for Hamiltonian outerplanar graphs, and I think its posible to extend the result, but ...
0
votes
1answer
33 views

Traveling salesman “with tunnels”

Like everybody on this website it seems, I have a traveling salesman problem. But the traveler wants to visit tunnels, so his exit points are not the entry points, he has to visit all of them, and his ...
0
votes
1answer
21 views

No triangles or rectangles in a Moore graph of diameter 2.

Can somebody explain why there cannot be any triangles or squares in a Moore graph with diameter 2? This was stated without proof in my class.
1
vote
2answers
37 views

cycle in a directed graph

Hi I saw in an R forum the answer: “If the graph has n nodes and is represented by an adjacency matrix, you can square the matrix (log_2 n)+1 times. Then you can multiply the matrix element-wise by ...
2
votes
2answers
20 views

The Petersen graph is 3-connected

This is obvious, but is there a simple/elegant way to show that the Petersen graph has no vertex cuts of size 2? One could just look at all possible vertex cuts of size 2 and observe that they don't ...
0
votes
1answer
7 views

Graph embedding in space: always possible?

Because graph theory is mostly concerned with embeddings on surfaces, I was wondering what would happen if we would consider higher-dimensional objects. My question is: can every graph always be ...
1
vote
0answers
11 views

implication of positive speed of random walk on a graph

Let $(V,E)$ be a vertex-transitive graph and let one vertex be the origin. Let $d(v,0)$ be the graph distance between $v$ and $0$. Consider $(X_n)$ a simple random walk on the graph. Let $A_n$ be the ...
-1
votes
0answers
54 views

Complement of a connected graph on three or more vertices is disconnected [on hold]

Prove or give a counterexample to the following statement: The complement of a connected graph on three or more vertices is disconnected.
2
votes
2answers
38 views

Upper bound for chromatic number

I'd love a hint in this problem, because don't know where to start. For any graph G it follows: $$\chi (G) \le 1 + \max\{ \delta (H):H \text{ is induced subgraph of } G\} $$ where $\delta (H) = \min ...
3
votes
1answer
33 views

Prove $\chi(G) \leq 1+\max\{\delta(H):H \text{ is an induced subgraph} \}$

Prove that for graph any simple graph $G$ we have: $\chi(G) \leq 1+\max\{\delta(H):H \text{ is an induced subgraph} \}$. Take $G$ and remove any vertex $v$ with degree less than $\chi(G)-1$. Do the ...
2
votes
1answer
18 views

Show that the t-cube $Q_t$ is has connectivity t

The t-cube $Q_t$ may be defined as the graph whose vertices are all the binary $t$-tuples. Vertices are adjacent iff they differ in exactly one component. [e.g. in the 3-cube $(0,0,0)$ is adjacent to ...
0
votes
0answers
9 views

Chromatic Polynomial Q_3

How to compute the chromatic polynomial of graph $Q_3$? Is it easy to compute? Can we use the fact $Q_3= Q_2 \times P_2$? Please give an idea.
0
votes
1answer
17 views

No complete graphs could be bipartitle.

How do I prove that the above statement is false? Can anyone give me a hint or so on how to disprove the above statement?
1
vote
2answers
35 views

Is showing a graph is non-Hamiltonian NP-Complete?

Show that graph is not Hamiltonian. Is this an NP-complete problem? My guess is that this is not an NP-complete problem, because we can run DFS and check it. Like, if we have a Hamiltonian cycle ...
0
votes
1answer
31 views

Probability that a random graph is connected

Let $V=\{v_1,\dots,v_n\}$ a set of $n$ vertices. Define $\mathcal{G}$ to be the set of all graphs on $V$. $|\mathcal{G}|=2^{\binom{n}{2}}$. What is the probability that a random graph from ...
2
votes
1answer
21 views

Does $G$ have a $(\chi(G)-1)$- regular induced subgraph.

If $G$ is a simple graph which has chromatic number $\chi(G)$ is it true to claim that there is a $(\chi(G)-1)$-regular induced subgraph? I've been trying to prove it. It seems as though it should be ...
3
votes
1answer
25 views

Prove that a simple critically 3-chromatic graph without isolated vertices has $\Delta(G)=2$

Can any one help me prove - A simple critically 3-chromatic graph without isolated vertices has $\Delta(G)=2$. I tried to do it by contradiction and show that if a vertex $v$ has degree 3 or more ...
1
vote
1answer
21 views

Is the disjoint union of 2 copies of the complete bipartite graphs vertex transitive?

Is the disjoint union of $K_{n/4,n/4}$ and $K_{n/4,n/4}$ a vertex transitive graph? I think it is true, but since I failed to come up with a proof I have some doubts about it. Thanks