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
1answer
40 views

Decomposing $K_v - K_u$ into Hamilton paths where $v = u^2 - u + 1$.

A decomposition of a graph $G$ into subgraphs $H$ is a collection of graphs all isomorphic to $H$ which are edge-disjoint in $G$ and together cover all the edges of $G$. Let $u \geq 1$ and $v = u^2 ...
0
votes
0answers
27 views

Isomorphism of complete DAG corresponding to group action on group ordering.

Label the complete directed acyclic graph nodes with elements of a group of size $|V|$ where $V$ is the set of vertices. This graph represents a total ordering $\lt$ of the group minus antisymmetry. ...
0
votes
0answers
39 views

Match Scheduling

Is there an algorithm for match scheduling implemented using vertex coloring? An example question for match scheduling is : Consider a tennis tournament with x players and y courts. Each player plays ...
0
votes
0answers
144 views

What is the equation for the average path length in a random graph?

If we have random network/graph having a number of vertices $N_v$ and there number of edges $N_e$, how do we calculate the average path length between two random ...
0
votes
0answers
209 views

A graph with 20 edges has 5 vertices of degree 5 with the rest of degree 4. How many vertices of each degree does it have?

Actually, I have an answer and it is pretty simple to be obtained. You just have to use the classical theorem that states that the sum of all degrees of the graph is equal twice the number of edges. ...
0
votes
1answer
55 views

unranking a sequence of all linear extensions of a partially ordered set

Let $P$ be a partially ordered set. Let $E$ be the set of all possible linear extensions of $P$. Let $S$ be the sequence formed by arranging elements of $E$ in lexicographic or graycode order. Does ...
0
votes
0answers
28 views

Practical use of Ramsey numbers [duplicate]

I am fascinated by the Ramsey number, but I was wondering, what are practical uses of the Ramsey number? Except for the party problem, I can not come up with something where it is useful for. Do you ...
0
votes
0answers
35 views

How to show this [duplicate]

Given $15$ lines in the plane, can anyone show that there are at least $3$ of the lines, such that the angle between any two of them is less than $\frac{\pi}{4}$?
0
votes
0answers
52 views

Travelling Salesman Problem with a pen

What's the best way to get a reasonable solution to the asynchronous TSP with a pen and paper?
0
votes
0answers
167 views

If vertex x has degree k in G what is it it's degree in complement of G

I am trying to answer this question..Initially I thought it was: (n choose 2 ) - # of edges in G = # of edges in complement of G (l) deg of vertex x = l-k However this doesn't work for some of the ...
0
votes
1answer
55 views

Difference between isomer and isomorph

In graph theory what is the difference between isomerism and isomorphism? I found a post somewhat similar to it but couldn't understand my problem from that. So I asked again specifically asking my ...
0
votes
1answer
60 views

edge disjoin Cut Set

prove that a graph G=(V,E) where | v | =n there are at most n-1 edge disjoint cut sets. I was thinking that for tree it is true since each edge is cut set. but i have no idea how to prove above ...
0
votes
0answers
68 views

material for graph theory practice

How to practice more on graph theory. My course book is Graph Theory by Narsingh Deo but still I want to go in more depth.Please refer links or preferable book.
0
votes
0answers
71 views

First event in a straight skeleton

Is there a simple geometric criterion to check whether the first event in (the wave propagation of) a straight skeleton is an edge event or a split event? The literature I could find is computational ...
0
votes
1answer
67 views

How do I prove that a graph if Hamiltonian it must be 2-connected?

I understand that a graph is biconnected if each vertex has degree > or equal to 2. Is it enough to say that a Hamiltonian Graph contains a cycle and every cycle has a least the degree of 2?
0
votes
0answers
99 views

a question about complete gragh

I have a conjecture but I can not proof it or find a counterexample.So I want to ask for some help.My conjecture is: Let G be a 2-connected (simple)gragh satisfy: (1)the maximal length of odd cycle ...
0
votes
1answer
52 views

Number of subgraphs of diameter d

I have a graph $G(V, E)$. I want to know the number of unique subgraphs with diameter d >= 1. I will give a couple of examples: 1) In the following graph, there is 3 unique subgraphs of diameter 1. ...
0
votes
1answer
38 views

Diffusion on a weighted graph

I have a weighted graph and want to apply a diffusion step to it. I read this paper, where they formulate such a diffusion step for unweighted graphs: $Z_i(t+1)=Z_i(t)+\alpha\sum_j ...
0
votes
0answers
31 views

What probability distributions are not decomposable on a full graphical model?

It is said that a distribution $p(x_1, ... , x_n)$ is decomposable over a graphical model if for all conditionally dependent vertices ($x_u, x_v$), the graphical model contains the edge $(u,v)$. ...
0
votes
1answer
22 views

Order embedding and graph embedding of Hasse digraphs

If there is an order embedding from order A to order B, is there a graph embedding between their Hasse digraphs? What if we replace 'embedding' by 'order preserving' and 'homomorphism' etc?
0
votes
0answers
30 views

spoting wrong weak edges on a graph (Is there anything like that?)

I've a question that I don't even know how to ask in order to start searching a way to solve my problem. Here is the Minimum Working Example(MWE) i can think of my problem: I've a graph were the edges ...
0
votes
0answers
108 views

Symbol for the incidence relation between vertices and edges.

Q: Suppose $G$ is a graph whose vertices are $V$ and edges are $E$. Is there a standard symbol for the relation $R$ on $V\times E$ such that $vRe \iff $ v is a vertex of $e$? ...
0
votes
0answers
97 views

how to proof $S^{2n+1}$ can be decomposed to one 2n+1 complex and $S^{2n}$can be decomposed to two 2n complexes?

Is there any reference refer to the question? The fact is apparent ,but i can't proof it.
0
votes
0answers
30 views

How to perform a stochastic search of the locality of a node in a network?

In a graph that may be a random graph (ER graph), scale free network, etc. I would like to obtain a distribution of the locality of the nodes surrounding a ...
0
votes
0answers
22 views

Possible to refine an orthogonal graph face into rectangles if it contains internal dead ends?

In Graph Drawing algorithms by Battista et al (chapter 5.4), a non-rectangular face with orthogonal edges is split into rectangluar faces by assigning turn values for each edge based on the turn ...
0
votes
0answers
45 views

Expected size of the largest cycle

Assume that given $n$, a graph $G$ is created randomly, so that each point is directed to any of the $n$ points (including itself) at random. (So self loop is possible.) Then $G$ is graph of $n$ ...
0
votes
1answer
92 views

Forming a graph

I'm trying to apply graph theory tools to a problem I'm working on, but am not sure it's possible to construct what I need. This isn't the whole problem, but the sticky part is this: I have three ...
0
votes
0answers
23 views

What is the formal name for my “line & node fixation problem”?

Background: Imagine I have 5 sticks in such a manner that $head_{1}$ is free, $tail_{1}$ connected to $head_{2}$, $tail_{2}$ to $head_{3}$, $tail_{3}$ to $head_{4}$, $tail_{4}$ to $head_{5}$, and ...
0
votes
0answers
61 views

What is the diameter of the largest strongly connected component in a directed graph?

Given a node of size $n$ and a probability of connection $p$, what is the diameter of the largest strongly connected components in a directed graph? I'm sure someone already made some nice theory ...
0
votes
1answer
44 views

Troubles solving a graph problem

I'm having troubles finding a solution to this problem. Having these datas, I'm supposed to prove that a 1 graph is possible. Here, $\Gamma^+(W)$ is the outdegree and $\Gamma^-(W)$ is the indegree of ...
0
votes
0answers
48 views

Counting unique weightings of a graph

Given an undirected unweighted incomplete but connected finite graph to which I then apply weights to the nodes and edges, I would like to count all of the unique weighted graphs that have the same ...
0
votes
1answer
69 views

How many friends of friends of friends?

I'm trying to determine how many second degree (friends of friends), and third degree (friends of friends of friends) a typical individual has based on the current number of friends he or she ...
0
votes
0answers
111 views

Variance of the first return time of a simple random walk on an hypercube graph

I am trying to solve this problem.... I have a simple random walk on a $d$-cube (finite graph). At each vertex of the graph, the particle chooses one of $d$ edges equally likely. I need to calculate ...
0
votes
0answers
48 views

a doubt over a term in paper of graph theory

I was reading a paper http://www.sciencedirect.com/science/article/pii/S0166218X08001960. On the page 38, under the topic The vertex hierarchy I have doubt. From where did the following term come? ...
0
votes
1answer
153 views

Does a graph contain a 3-cycle or a 4-cycle

Given a graph $\mathscr G$, that has 100 nodes each with a degree can you show that this graph contains a 3-cycle and/or a 4-cycle? The graph in question represents 100 people at an event, and they ...
0
votes
0answers
64 views

Lifting automorphism problem - classical approach

Let X, Y be connected graph and Y be a covering graph of X and A be asubgroup of Aut(X). let B be lift of A. we know there is a group epimorphism from B to A. What is this epimorphism?
0
votes
0answers
54 views

Is there a special name for planar graphs, when the outer face has the highest degree?

Is there a special name for planar graphs, when the outer face has the highest degree? $\hskip1.3in$ Like $a)$, where $f_{\text{outer}}=6$; not like $b)$, where $f_{\text{outer}}=4$...
0
votes
1answer
88 views

Algorithm of creating dual graph from a plannar graph

Depite i have some ideas to create a dual graph from a planar graph, but i prefered to ask it here. Is there any algorithm for this purpose? Thank you so much.
0
votes
0answers
74 views

Returning paths of length $L$ in cubic planar graphs with the property $\mathfrak E$

I'm looking for a special kind of returning paths of length $L$ in cubic planar graphs with the property $\mathfrak E$, that when I write down the times a certain vertex is visited, no vertex has the ...
0
votes
1answer
31 views

Is there an algorithm for computing planar embeddings for non-biconnected graphs?

Every algorithm I've found so far begins by computing st numberings, which in turn requires a biconnected graph in order to work with an arbitrary vertex pair (s, t). In the following graph, edges ...
0
votes
0answers
37 views

simplifying an equation [duplicate]

I gave details here of my last question...I hope this helps I am having doubt over an equation. That is my calculation. Can anybody check and find the error, if any. Specially in the last line. I am ...
0
votes
1answer
106 views

Solving the travelling sales person problem for the graph.

If I'm asked to "[s]olve the travelling sales person problem for the graph," am I asked to just find it manually? If not I could write some code to find the answer if I had a way to catalog the ...
0
votes
0answers
37 views

Proving a fact about planar graphs

Let $G$ be a connected planar graph with $p$ vertices and $q$ edges and girth $k$. Show $$q\leq {k(p-2) \over k-2}$$ How should I do this? My textbook has no solution, and I seem to not recall ...
0
votes
0answers
30 views

A super class of bipartite graphs

For a graph $G$ on $n$ vertices $1,\ldots,n$, let $N^-_{i,j}=\{k:k\sim i, k\sim j \mbox{ and } k<i,j\}$, $N^+_{i,j}=\{k:k\sim i, k\sim j \mbox{ and } k>i,j\}$ and $N^0_{i,j}=\{k:k\sim i, k\sim j ...
0
votes
1answer
87 views

How can I find the cut vertices from this graph?

$G = (\{a,b,c,d,e,f\}, \{\{a,b\}, \{b,c\}, \{c,d\}, \{d,e\}, \{e,f\}\})$ implies the following are cut vertices: a b c d e f Is each group of vertices in the list a ...
0
votes
0answers
35 views

How to choose the adjacency set

Given a group $G$ of order a composite number, how should one construct the adjacency set $S$ such that the underlying Cayley graph $\Gamma=\text{Cay}(G,S)$ admits a block system under ...
0
votes
0answers
12 views

How to remove all the parent cycle s in a graphycle 1 => that contain atleast one child cycle?

The following are the points of Cycles:- Cycle1=> {1,2,4,6,7} Cycle2=> {2,3,5,6,7} Cycle3=> {1,3,4,5,6,7} I want to remove the cycle 3 because it contains Cycle 1
0
votes
1answer
31 views

Is this graph transitive?

I have a graph $G = (A,B)$ which is transitive when: $(a,b) ∈ B ∧ (b,c) ∈ B → (a,c) ∈ B$. How can I prove that $G$ is transitive iff it's acyclic?
0
votes
1answer
39 views

Split graph into groups of edges that are not adjacent

I need to split graph, another say to color it into some groups of unadjacent edges. Minimize number of groups is not the only goal to achive. Group of every size has its's own weight, e.g. 64 - 1, ...
0
votes
0answers
52 views

Medium-strong (graph) homomorphisms

Weak (graph) homomorphisms are mappings $f: V(G) \rightarrow V(G')$ such that the images of connected nodes $x,y$ (in the source graph) are connected: $$R(x,y) \rightarrow R(f(x),f(y)) = R(x',y')$$ ...