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
16 views

The value of m(n) when n = 3

Let's consider hypergraph $G_n(V,E)$ such that for every $e \in E, ~|e| = n$. We define $m(n) = min(|E|: \exists G_n(V,E): \chi(G_n) > 2)$. I'm confused with the problem of finding the value of ...
0
votes
1answer
19 views

Complements are also paths

i am new to graph theory and in one of the lectures notes i found a lemma about the paths of a graph and its complements? LEMMA:There are only two graphs such that their complements are also ...
2
votes
1answer
36 views

What is the “true” minimum spanning forest of a connected graph?

Normally, a minimum spanning forest of a graph G is defined as the union of minimum spanning trees of each of its components. This definition is a generalization of the minimum spanning tree of a ...
0
votes
0answers
31 views

About Katz centrality

I am studying Graph Theory and Network Analysis, I have this measurement formula which called Katz centrality: My question is: why $A^k$ will grow [infinitely] in $k$ for most cases. As I think ...
2
votes
1answer
17 views

Show that every finite plane graph where every vertex has even degree has a 2-face colouring.

I want to attempt to do this by using induction on the number of edges. Trivially it holds for $K_3$ and then if you remove two edges from a boundary of a face with the outer edge. Apply the Induction ...
0
votes
1answer
31 views

Proving that these graphs are not isomorphic

I have these three graphs (in the image below, sorry for poor quality it's on microsoft paint) http://i.imgur.com/oAc785t.png I need help proving that X is not isomorphic to Y and that X is not ...
-1
votes
0answers
12 views

How to test if a tree fit in existed hypothesis?

Saying I have some data, and I build a tree based on the data. Now I want to test if this tree fit in my predefined hypothesis statistically. How can I do it? For example, the null hypothesis is the ...
1
vote
0answers
24 views

Probability of relations in a network

Imagine, i have a predicate $\text{friends}(x_1, x_2)$ and I know that $p(\text{friends}(x_1, x_2)) = p_2$. If I generate a world of $n$ people ($x_1$ to $x_n$), I expect there to be $\binom{n}{2}p_2$ ...
0
votes
0answers
27 views

Is the following algorithm for finding the minimum diameter spanning tree correct?

You are given an undirected and unweighted connected graph $G(V, E)$ for which you've been asked to find a spanning tree that has minimum diameter. I have an idea but I'm not sure if it's a ...
1
vote
2answers
31 views

Why is it that no bipartite graphs contain a triangle?

I know it has something to do with the vertices belonging to two differnt sets without intersection but I'm not exactly sure of a concrete explanation. Thanks in advance.
1
vote
1answer
41 views

Why does there not exist a 3 regular graph of order 5?

Because the lines of a graph don't necessarily have to be straight, I don't understand how no such graphs exist. Can anyone shed some light on why this is?
-2
votes
0answers
19 views

Looking for examples of path finding algorithms that use “metagraphs”

I don't think this is the right term (metagraphs), but it seems appropriate. I'm looking for any examples of path finding algorithms that take 2 graphs into account, G1 and G2, where a copy of G2 is ...
4
votes
2answers
55 views

Labelings of infinite directed acyclic graphs

Let $G=(V,E)$ be a countably infinite directed acyclic graph and $L$ be a finite set of vertex labels. The number $\left|V\right|$ of vertices is countable infinity and some vertices may have an ...
1
vote
0answers
29 views

Generalization of vertex transitivity

I understand vertex transitivity of a graph $G$ as the property that the local environment, i.e., all incident edges and their vertices, of any 2 vertices looks the same. What if we extend this ...
3
votes
2answers
178 views

Minimum possible number of vertices in a tree with restrictions on vertex degree

I am confused with this question. My teacher asked us at class but I cannot solve it. Can you help me? "Let $T$ be a tree with exactly two vertices of degree $7$ and exactly $20$ vertices of degree ...
2
votes
1answer
44 views

Graph: question on planar graph.

I have a lemma that say: Let $G$ be a planar graph whose exterior face is bounded by a cycle $u_1,...,u_k$. Then there is a vertex $u_i$ ($i\neq 1,k$) not adjacent to any $u_j$ other than $u_{i-1}$ ...
0
votes
0answers
24 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
1answer
31 views

Property of simple bipartite graphs [duplicate]

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
21 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
1answer
29 views

Circuits and cutsets in graphs [on hold]

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
33 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
79 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
28 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
43 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
8 views

Vertex invariant based on minimal neighbourhood

A possible vertex invariant of a graph G is the smallest k-neighbourhood of a vertex v such that the k-neighbourhood of v has only one isomorphism to G. This is of course not possible if G has ...
0
votes
0answers
13 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
48 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
41 views

Graph Theory-maximal path [closed]

Can anyone please draw this, I have been trying to draw for a long time
1
vote
1answer
32 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
29 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
44 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
24 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
43 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
22 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
19 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
19 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
3answers
62 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
25 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
29 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
81 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
27 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
37 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
316 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
15 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 ...
1
vote
1answer
40 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
26 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
44 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 ...
3
votes
2answers
24 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 ...