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

Pairwise crossing lines meaning

I'm having a hard time being certain of the meaning "pairwise crossing" in the context of Graph Theory... namely, if say 4 lines are pairwise crossing, may any be parallel. the question states: "A ...
1
vote
0answers
19 views

Connected graph G is complete bipartite iff no induced subgraph of G is a $K_3$ or $P_4$

Where $K_3$ is a triangle and $P_4$ is a path of 4 vertices. One implication is here the other one: If $G$ is a connected complete bipartite graph, it cannot contain any triangle induced, because ...
0
votes
2answers
29 views

Traveling salesman problem (TSP): what is the Relation with number of vertices and length of the found route?

I know that there are many algorithms (exact or approximate) which implement the traveling salesman problem. I would like to know the relation between the number of the vertices (i.e., the places to ...
-4
votes
1answer
28 views

Proving some problems in graph theory [closed]

Suppose that a graph $g$ and its complement are both connected graphs of order $n>5$. Prove that if the diameter of $g$ is at least $3$, then the diameter is at most $3$.
0
votes
1answer
31 views

Are these graphs homeomorphic?

Are these graphs isomorphic, and why? In advance, thanks!
3
votes
1answer
63 views

Need a counter example for cycle in a graph

Could anyone give a counter example for that theorem : A graph G has exactly one vertex of degree $1$, then it contains a cycle. I am so confused. I wonder that may I give a counter example ...
0
votes
2answers
70 views

Sum of squares of distances between all vertices in tree

Given the adjacency list of unweighted undirected graph without cycles, calculate sum of squares of distances between every two vertices. How to do this fast? (programming task)
-1
votes
1answer
46 views

A graph with exactly one vertex of degree one contains a cycle? [duplicate]

A graph $G$ with exactly one vertex of degree one contains a cycle. Is there any counter example? I could not find any graph for counterexample. Please help.
0
votes
0answers
20 views

Node potentials of minimum cost flow successive shortest path algorithm

I have a simple directed graph $G(V,E)$ that has a source $s$ and sink $t$. Each edge $e$ of $G$ has positive integer capacity $c(e)$ and positive integer cost $a(e)$. I am trying to find the minimum ...
0
votes
2answers
33 views

Rumour/Gossip theory problem to simulate fire propagation.

I have a set of planar graphs I am using to model a landscape. I am trying to model fire propagation. So if say fire starts at node A, there is a chance that fire can propagate to all of A's adjacent ...
4
votes
0answers
49 views

What are some other examples of this phenomenon: if $S$ is a finite set, then all possible total orderings of $S$ are isomorphic (as posets).

Finite sets have the amazing property that if $S$ is a finite set, then all possible total orderings of $S$ are isomorphic (as posets). Said another way: finite totally-ordered sets that are ...
2
votes
0answers
81 views

ZELDA Guardian Puzzle Part II - Shortest Path (Unsolved for new rules)

This question is in relation to the following previously asked question: Twilight Zelda Guardian Puzzle : Shortest Path (UPDATE: ADDED RULES) A 1-step-less solution was uncovered, but under an ...
2
votes
1answer
20 views

Perfect matching problem

We have a random graph G = (V,E). Two players are playing a game in which they are alternately selecting edges of graph so that in every moment all the selected edges are forming a simple path (path ...
2
votes
3answers
147 views

What is the maximal path of a tree?

Could anyone explain obviously what the maximal path is ? Is it necessary for a tree that has two maximal paths that share no common vertex ?
0
votes
0answers
19 views

Prove that the circuit rank $= |e|-|v|+c$ , where $c$ is the number of connected components?

How to prove that for any given graph $G=(V,E)$, the circuit rank is $$|E|- |V| + C,$$ Where $C$ is the number of connected components.
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
33 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
22 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
26 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
54 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
177 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
29 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
23 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
20 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
28 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
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
74 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
27 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
41 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
6 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: I'm wondering if this notion ...
0
votes
0answers
12 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
31 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
27 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
38 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
22 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 ...