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

1
vote
0answers
55 views

Prove that a finite complete graph can be embedded in $\mathbb{R}^3$

I've actually found a few intuitive examples where edges are taken to a twisted cubic and and the vertices are arranged in a certain way and that's very nice, but I'm actually more interested in a ...
1
vote
0answers
44 views

Intuitive understanding of 'Graph Limits'

I've been trying to understand the concept of Graph Limits (In particular, the following paper by Lovasz 'Limits of dense graph sequences') for a particular project of mine. I'd like to know if ...
1
vote
0answers
66 views

Digraphs: Is this an example of a digraph with no cycles, but a closed walk?

I'm trying to apply this vocabulary: cycle and closed walk on a digraph. So since a cycle is a walk such that all the vertices are different except the last two, and a closed walk is just a walk that ...
1
vote
0answers
60 views

computing dual LP in graph matchings

I'm having a trouble converting the following LP to a dual LP. Help on some starting steps would be greatly appreciated!
1
vote
0answers
48 views

regular graph (dividing vertices togroups of edges and circles)

Let G be a regular graph. Prove that it's vertices can be divided to groups of either edges or circles. Assuming we are looking at a K-regular graph, I was testing the effect of K being odd or even. ...
1
vote
0answers
42 views

fitness cost calculation finding the weighted sum

I am having a little bit of trouble making a weighted sum calculation for subpaths(Where subpath is the path between two cities e.g. A->B) in a travelling salesman problem. Basically I have 3 ...
1
vote
0answers
143 views

relationship between kruskal algorithm and TSP

Question $8$: Is the TSP tour obtained in Question 7 optimal? For question $6$, I got total weight is 60. Edges are $1-2, 2-4, 3-4, 3-9, 5-6, 6-7, 7-8, 8-9$ Question $7$: We need to add the edge ...
1
vote
0answers
47 views

Isomorphisms from $K_5$ to points in $\mathbb R^4$

Is there an isomorphism from the complete graph $K_5$ to a triangular solid in $\mathbb R^4$? For example $K_3$ is trivially mapped to a triangle, $K_4$ may be mapped to a tetrahedron, so what about ...
1
vote
0answers
117 views

Number of paths through an incomplete graph (with restrictions)

Here's a question I came upon while fiddling around with yarn on spindles. I joined three spindles so that they were orthogonal.. then, beginning at the base of a particular spindle (A), wound it ...
1
vote
0answers
41 views

On graph homomorphism properties

Let $G,H$ be finite graphs with $|V(H)| > |V(G)|$. Let $\mathcal{f}:G\rightarrow H$ be an injective homomorphism - that is, $\mathcal{f}$ is: $1.$ Injective - ...
1
vote
0answers
273 views

How to show that union and intersection of min cuts in flow chart is also a min cut

The proof of this is everywhere skipped and said to be collorary of Ford-Fulkerson theorem. It's usually something like: Let $A$ and $B$ be low cuts of a flow chart. Then $A \cup B$ and $A \cap B$ ...
1
vote
0answers
44 views

What does it mean for two graphs to be consistent

I am trying to understand what does it really means for two graphs to be consistent in the context of bidirectional transformation ? Can you provide me with a good example? Thank you in advance.
1
vote
0answers
24 views

Terminology for a graph that can be drawn in several planes?

A graph is called planar if you can draw it in the plane without any edges crossing. In circuit layouts, it's common to try to lay out a graph across multiple different planes, where edges can jump ...
1
vote
0answers
57 views

Mathematical research on ground state configuration of ising model

I want to do mathematical research (algorithm construction and mathematical analysis) on ising model ground state configuration. From what I know, the state of art research is using graph theory ...
1
vote
0answers
81 views

Graph theory name for minimum depth to leaf node.

In a graph theory rooted tree, is there a name for the minimum depth downwards to reach a leaf node? I have in mind calculating "depth to a leaf" at each node by looking downwards through the subtree ...
1
vote
0answers
90 views

Odd problem about graph connectivity

This problem asks how to prove that a graph has k-connectivity. However, there's something which makes the problem intricate. The graph which I'm studying about is a graph with 2k-2 vertice and the ...
1
vote
0answers
62 views

Recommend an intro to binary embedding algorithm in Graph Theory

I'm working on my final year project which will establish an reasonable upper bound for one of the bandwidth problem in graph theory. I found difficulty on understanding an algorithm that construct an ...
1
vote
0answers
33 views

Graphs: First Order Characterisation Of A path

Whilst reading this: http://dtai.cs.kuleuven.be/krr/files/seminars/IntroToFMT-janvdbussche.pdf a seminar on finite model theory, I thought that something was wrong. "Given a Graph G and a Binary ...
1
vote
0answers
19 views

Determine the multiplicity of knots for a graph

Here are my two questions: Given a finite connected non-oriented planar graph, is there a way to determine whether or not it is possible to derive a single non-trivial knot diagram from this graph, ...
1
vote
0answers
119 views

Node mapping with edge weights

For an academic paper, I wish to use node mapping and weighted edge. I do not understand the concepts quiet clearly. I have a weight on each edge. The graph for which am trying to solve the problem ...
1
vote
0answers
73 views

“Das ist das Haus vom Nikolaus” and Euler cycle

Consider the following graph $(V,E)$: With $a, b, c, d, e \in V$. Then I obviously can make an Euler cycle: $[b, a, c, e, d , c, b, e, a]$. But it also holds that $deg(a)=deg(b)=3$ which is not ...
1
vote
0answers
46 views

automorphism of a rooted tree

Nowadays i'm working with tree automorphisms. I couldn't find information about rooted tree automorphism concerning the root. Does an automorphism of a rooted tree fix the root or not? Logically it ...
1
vote
0answers
127 views

prove matroid conditions

can anybody please help me to prove bicircular matroid is a matroid, from the direct definition of bicircular graph, it is also called pseudoforest. So we define the independent set to be the edge ...
1
vote
0answers
56 views

Types of symmetry for combinatorial graphs

Let $G$ be an undirected, connected graph without loops. Let's call $G$ symmetric iff it has a non-trivial automorphism (that is a permutation $\pi : V(G) \rightarrow V(G) $ – which is not the ...
1
vote
0answers
82 views

Expected distance traversed between 2 vertices on probabilistic graph

Let $V = \{1,2,3,...,N\}$ be the vertex set of a graph. Let $d(i,j)>=0$ represent the $(i,j)$ vertex distance between vertices $i$ and $j$, $i \in V, j \in V$. Now, define a non-negative number ...
1
vote
0answers
33 views

Embeddings and Covering faces?

I have a dude with the following problem. Suppose you have an 2-cell embedding of some simple graph $G$ on a orientable type surface $S_g$ (for example a plane graph), and you desire to find a set $A ...
1
vote
0answers
90 views

A question on graphs

Do there exist a family of graphs with $\Omega(N_{G}^{c})$ edges for some fixed $c > 0$ with the property: $$\left|\alpha\left({G \boxtimes \bar{G}}\right) - \alpha\left({\overline{G \boxtimes ...
1
vote
0answers
31 views

Graph class of a “polygon tree”

A cycle is a polygon tree. A new polygon tree $G′$ can be created out of an existing polygon tree $G$ by adding a cycle which shares exactly one edge with graph $G$. I want to know which graph class ...
1
vote
0answers
86 views

A basic intuitive question on basis

From Zorn's lemma, basis can be thought of as a maximal independent set as well as minimum cover (covering all the vectors). Is this observation correct ? Can this observation be related to the usual ...
1
vote
0answers
80 views

What is the tutte polynomial

I am really stuck on how to work out the tutte polynomial so any help would be great thanks. G is a graph with 2 vertices, joined by n edges. How to you show what the tutte polynomial is? And what ...
1
vote
0answers
44 views

Highest known minimum bipartite crossing number?

I'd like to know what the highest known complete bipartite minimum crossing number graph K is? Last I knew it was K 7,7 , has K 8,8 been conjectured or proven yet? Any info on where I could find ...
1
vote
0answers
36 views

Possible number of endofunctors

The discrete category with countably many objects and morphisms has uncountably many endofunctors (= the number of functions from $\mathbb{N}$ to $\mathbb{N}$). Which categories with countably many ...
1
vote
0answers
37 views

Routing in a faulty hypercube

Suppose I colored a fraction (say $e$) of the edges of the $n$-dimensional hypercube. (the set $\{0,1\}^n$, with edges between points which differ by a single coordinate) Let $c<0$ be some ...
1
vote
0answers
73 views

automorphism group of connected cubic symmetric graph

I want to cumpute |Aut(X)| when X be a connected cubic symmetric graph. Let X be a connected cubic symmetric graph. Automorphism group of X act on vertex set, V(X). Let u be a vertex of X.We know ...
1
vote
0answers
50 views

Fixed Length Cycle Search

I am given a list of $0 \le M \le 2n(n-1) $ edges of a graph. My goal is to find a connected subgraph of this graph such that the degree of every vertex in the subgraph is $n$ that has exactly $n$ ...
1
vote
0answers
28 views

Union of preimages of edge coloring

Let $G=(V,E)$ be a graph and $c:E \rightarrow [\chi'(G)]$ be an edge coloring with chromatic index $\chi'(G)$. It is obvious that the preimage $c^{-1}(i),i\in [\chi'(G)]$ is a matching, but what can ...
1
vote
0answers
133 views

Prove a general version of Euler's formula

For a planar embedding of a graph $G$ with $n$ vertices, $m$ edges, $s$ faces and $c$ components, prove that: $n-m+s=1+c$ I have no real clue as to how to prove this, can someone help me?
1
vote
0answers
100 views

Subset of graph with minimum nodes minimum edges pointing out of the subset

Given a Directed Graph $G$ and a node $n$ in that graph I'd like to find a subgraph $S$ of $G$ with the following conditions: $n \in S$ $a * $ number of nodes in $S$ + $ b * $ number of edges going ...
1
vote
0answers
61 views

What is the complexity of finding a maximum size independent set in self-Complementary graphs?

A self-complementary graph is isomorphic to its (edge) complement. My question is whether finding a maximum cardinality independent set remains hard on this class of graphs. It is known that for some ...
1
vote
0answers
46 views

When zero-divisor graph is planar?

I need specific conditions that are completely exhausted class of Rings zero divisors graph of which are planar. Thank you.
1
vote
0answers
58 views

Coloring figures of isoceles right triangles

Are figures of isosceles right triangles known to be 3-colorable? I'm considering the graphs induced by figures of finitely many non-overlapping (no common interior points) isosceles right triangles ...
1
vote
0answers
99 views

Algebraic characterization of being $P_n$-free.

Is there an algebraic way to determine from the adjacency matrix $A$ of a simple graph $G$, whether $G$ contains an induced path of fixed length $n$? I am particularly interested in the case $n=6$. ...
1
vote
0answers
195 views

k6 embbeding on orientable surface of genus 3 with 6 pentagons faces

I need embbeding K6 on orientable surface of genus 3 . but I was asked to do it with the next stipulation : 5 faces only and all the faces in the embedding will be pentagons . In my opinion the way to ...
1
vote
0answers
129 views

High betweenness but relatively low degree, and its opposite

I'm a CS major working on social network analysis and its friends. In page 15 of this lecture note, two very interesting questions have been asked. Given a social network graph, in which cases would ...
1
vote
0answers
53 views

A family of $8$-regular Ramanujan Cayley Graphs

I'm looking for expander graphs with certain properties. Is there a family of $8$-regular Ramanujan Cayley graphs $\{\text{Cay}(G_n,S_n)\}_n$ such that each of them has no cycles of odd length? ...
1
vote
0answers
68 views

Characteristic polynomial of the tree

How can one show that a coefficient of $\lambda^{n-2k}$ in characteristic polynomial of the tree is a number of matchings of size k in this tree. $n$ is a number of vertexes in the tree.
1
vote
0answers
48 views

Topological graphs

Given the universel covering space $\hat{X}$ of $X$ by $p:\hat{X}\rightarrow X$, there exists a bijection between subgroups $H<G=\pi_1(X,x_0)$ and covering spaces $\tilde{X}\rightarrow X$ with ...
1
vote
0answers
60 views

How is this kind of subgraph called?

Consider a certain directed graph, G, and one of its subgraphs, S, such that: S is a strongly connected component of G, There are no paths from nodes in S to the rest of G, There is a path from ...
1
vote
0answers
53 views

understanding the basic definiton

I was going through a topic on $Product$ $Graphs$. I have a very small doubt in the definiton of $Lexicographic$ $Product$. It is defined as follows..... Given graphs $G_1$,$G_2$, . . .,$G_k$, we ...
1
vote
0answers
92 views

Threshold dense adjacency matrix

I have a dense, adjacency matrix (square, symmetric) representing a graph. I want to threshold that graph so that it only contains the largest weights (cells in the matrix), but is still fully ...