# Tagged Questions

68 views

### Graph theory / vertex-set list representation

If I were to consider a graph with vertex-set V= {1, 2, 3, ... 10} with the edges taken as all the pairs {x, y} of distinct members of V that have a prime factor in common, how would one write the ...
36 views

### Width and height of binary tree is $\theta(n)$?

we know this definition: Given a binary tree, Width of a tree is maximum of widths of all levels. Let us consider the below example tree. ...
41 views

### Graph Degree and Some Condition

If $G$ be a Tree with degree $(5,r,s,1,1,1,1,1)$. (I wrote degree in non-increasing order). why all of this condition is True sometimes (I means on some condition)? I try to find an example that ...
44 views

### Partition Graph Challenging Question

I want to find in which of the following Graph, the edges cannot partitioned to triangles? Km,n,r means 3-Partite Complete Graph with m, n, and r sections. a) K7 b) K12 c) K3,3,3 d) K5,5,5 i ...
18 views

### Planner Combination Problem on Graph

I ran into a Graph Problem. Suppose G is A Planner Graph with 100 Vertices such that if connect each two Non-adjacent vertices, the resulting graph would be non-planner. what is the number of edges ...
44 views

### Perfect Matching Combination Problem

We know: A perfect matching (a.k.a. 1-factor) is a matching which matches all vertices of the graph. if we remove edges of perfect matching of a 12-Complete Graph. how many triangle remain in this ...
38 views

### Check if there's a cycle in an undirected graph

I'm trying to find an algorithms that checks if there's a cycle in a given undirected graph G=(V,E). But I didn't succeed. Can anyone give me such an algorithm?
70 views

### Shortest path between wikipedia articles

I'm trying to figure out whether it is possible (and if so how) to find the shortest path inside a network from one node to another. I know that there are different possible algorithms to do that the ...
26 views

### Computer program for decomposing a graph into subgraphs?

Obviously there are programs out there that can find perfect matchings. I am interested in finding out if there is a program that can, for instance, tell when graphs like the cube graph $Q_n$, has ...
25 views

28 views

102 views

### How to Enumerate of all simple connected labeled graphs with prescribed degree sequence?

For v=4 vertices, there must be 7 possible graphic sequence (3,3,3,3)(3,3,2,2)(3,2,2,1)(3,1,1,1)(2,2,2,2)(2,2,1,1)(1,1,1,1). From (3,3,3,3), one simple graph(complete) can be found. From(3,3,2,2), 6 ...
127 views

### Finding the shortest/“most negative” closed directed trail in a weighted digraph with negative weights

I'm using the following definition of a "closed directed trail": a closed directed trail is a directed cycle in a digraph where all edges are distinct. Note that vertices may be repeated, so long as ...
87 views

### Finding a matching to connect subsets of vertices

I'm studying a graph problem which, strangely, has applications in bioinformatics. I'm not asking for a solution, but rather for advice as to whether something similar to what I do has been studied ...
88 views

### Describe a graph through logic

At the moment I'm in need to learn how to describe a graph through a logic statement such as:  \forall x\forall y(r(x,y) \to \lnot s(y,x) \land \lnot s(y,x)) \land \exists (s(z,z) \land \lnot ...
380 views

### Prim's algorithm

Given a connected, directed and weighted graph, Prim's algorithm may not necessarily generate the minimal spanning tree. Suppose we have such a graph $G$ with the special condition that for every pair ...
111 views

### 2-colorable belongs to $\mathsf P$

To show that 2-colorable belongs to $\mathsf P$, I have a straightforward mental description in mind that I don't think will be considered as a formal proof. Hence I am interested to know how this ...
1k views

### MATLAB code to find distance and eccentricity in graphs

I was trying to find the distances between vertices in graphs. But as the number of vertices are increasing up to 25 vertices or more, its becoming a tedious job for me to calculate $distance$ and ...
84 views

### Pebble game on graph

Consider the problem whose instance is a directed graph with the selected vertex V and k of 'pebbles'. We can in any order, perform the following elemental steps: on top of x we can put a pebble, if ...
We know that if in a graph $G$, $e$ < $(n -1)$, then the graph is disconnected, where $e$ and $n$ are number of edges and number of vertices resp. Is there any other criteria to find out the ...
### is the $d$-dimensional arrangement of Trees still $NP$-hard?
The $d$ dimensional Arrangement Problem for general graphs is known to be $NP$-hard since the special case $d=1$ (OLA) already is (Garey et al, [1976]). For Trees however, the one dimensional case can ...