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
2answers
48 views

Right way of getting degrees of vertices

Suppose I have the following list of nodes: A E G A E H A F G A F H B E G B E H B F G B F H C F C E D G D H Every line indicates the connections between those nodes. So there is a connection ...
0
votes
0answers
16 views

The modularity formula of Newmann and Girvan

I have question concerning the modularity formula of Michelle Girvan and Mark Newman. It says that it measures the fraction of edges in a network, that connects nodes, within the same ...
0
votes
1answer
23 views

Euler's formula about graphs embedded in $\mathbb{R^2}$

State and prove Euler's formula about graphs embedded into $\mathbb{R^2}$ I know that if we suppose $ G $ is a finite connected graph drawn on the surface of a sphere $ S^2 $. Then the ...
0
votes
0answers
22 views

Directed Weighted Graph with no cycles - LP

I have directed weighted graph. I have to find a set of edges with minimal sum of their weights that without the set graph becomes acyclic. I can call lp solver multiple times. I'm kind off lost on ...
-4
votes
1answer
69 views

First scientific work. [closed]

One year ago I decided to myself to write my own scientific work in number theory, graph theory or combinatorics. I tried to find the teacher and theme during this year, but unfortunately I didn't ...
0
votes
0answers
9 views

Multi modal transport network and graph theory

I am attempting to model a multi layered transport graph with points that allow for travellers to laterally transfer between graphs, in order to make use of different transport nodes. Conceptually, ...
0
votes
1answer
26 views

Graph theory notation misunderstanding

I know $K_n$ means the complete graph on n vertices. But in my lecture notes it said "Consider $2K_n$. Please could you tell me what this means?
4
votes
1answer
104 views

List of $n$-bit strings that approximately preserves Hamming distance

If $x$ and $y$ are both $n$-bit strings then their Hamming distance $d_H(x,y)$ is the number of positions in which they differ. Suppose we write out the set of all $n$-bit strings in some order $s_1, ...
0
votes
0answers
15 views

Minimum number of $m \times m$ matrices needed to recover a single large matrix

This problem was motivated by the need to efficiently train a neural net on a dataset in which the labels represent dependencies between examples, but nothing about it is machine-learning specific so ...
1
vote
1answer
23 views

How do I prove that the vertex chromatic number of a subgraph is less than that of the original graph?

How do I prove that the vertex chromatic number of a subgraph is less than that of the original graph? Say I have a graph with chromatic number $k$. How do I prove that the chromatic number any ...
0
votes
0answers
13 views

Finding a circuit in a weighted graph with weight closest to desired value

In an edge-weighted graph, is there an algorithm to find a circuit starting from a certain vertex, where the sum of the weights on the circuit is closest to a desired value? For instance, say I want ...
1
vote
1answer
32 views

Definition of Perfect Elimination Ordering?

The answer to this question could be trivial ! Definition: According to the wikipedia page: A perfect elimination ordering in a graph is an ordering of the vertices of the graph such that, for each ...
1
vote
1answer
86 views

Chess kings number of arrangements

How to find $2500$ chess kings number of arrangements on board $100\times100$? Is it possible to do that with just combinatorics? Will it be less then $(51^{50}\times2^{2500})$ and $(51^{100})$
0
votes
0answers
21 views

Does bipartite graph that $|X|=|Y|=n$ and $d(G)\ge \frac n2$ ; has complete matching?

A bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint sets and (that is, and are each independent sets) such that every edge connects a vertex in to one in . And ...
0
votes
0answers
13 views

Existence of some well known family of generalized graphs

I am in interested to know about some well known family of generalized graphs. Till now, I am aware of only one generalized family of graphs : Generalized Petersen graphs. Is Generalised quadrangles ...
0
votes
0answers
7 views

Prove that chromatic number of a graph is less than the chromatic number of its Hajos graph.

Prove that $\chi (G) <= \chi (H (G,v_1,v_2)) <= \chi (G-v_1v_2) + 1$, where $H (G)$ is the Hajos graph of g.
3
votes
0answers
24 views

Diametrl path of a graph

Let $G(V,E)$ be a graph. A path whose length is equal to the diameter of a graph is called a diametral path. In a cycle graph every vertex has $2$ diametral paths. Now I need to prove that this: ...
1
vote
1answer
27 views

Calculate the number of SDR's in $A_i:=\{1,\dots,n\}\setminus\{i\}$

Suppose that $A_1,A_2,\dots,A_n$ are sets, which we refer to as a set system. A (complete) system of distinct representatives is a set $\{x_1,x_2,\ldots,x_n\}$ such that $x_i \in A_i$ for all $i$, and ...
0
votes
0answers
18 views

Domain of Injectivity of Analytic Map

Suppose we have an analytic map $f: \mathbb{D} \to \mathbb{C}$. Then the set of points where the function is not locally injective is a discrete set. Suppose first for simplicity that the points ...
1
vote
1answer
61 views

Is the category of simple graphs finitely complete?

I have read (on nLab and wikipedia) three conflicting statements: The category of simple graphs is finitely complete The category of simple graphs has no terminal object A category is finitely ...
0
votes
0answers
14 views

How do you find the expected Cover Time of a graph?

I can only find resources that give an upper bound on the cover time, but not how to find the exact expected cover time of a graph. Somebody told me it's related to the coupon collector problem, but I ...
0
votes
0answers
12 views

$\epsilon$-regular bipartite class

Suppose that $G$ is a bipartite graph, with vertex classes $V_1$ and $V_2$ each of size $n$ and the maximum degree of $G$ is at most $\epsilon^2n$. Then show $(V_1, V_2)$ is $\epsilon$-regular in $G$. ...
1
vote
1answer
16 views

Tests for my “LineGraph-from-AdjacencyMatrix” function

I think I found a way to generate adjacency matirices $L$ of line graphs from the adjacence matrices $A$ of graphs. Now I want to test my function $L=f(A)$. When $A$ is the cube, $L=f(A)$ already has ...
0
votes
0answers
11 views

What condition can I impose on a graph to know the properties of certain subsets

I am sorry for the question being a bit open. I ran into this definition while working on a non graph theoretic problem. I am not a graph theorist myself and I have no idea how to look it up. Any ...
0
votes
0answers
14 views

Problem with Hall's marriage theorem

Let P1={A1,A2,...,A10} and P2={B1,B2,...,B10} be two distinct partitions of a set of 100 people into groups of 10. Let G be a bipartite graph with P1 and P3 as bipartitions. There is an edge between ...
1
vote
1answer
18 views

Is Graph with multiple-inputs and multiple-outputs called MIMO?

MIMO (systems with multiple-inputs and multiple-outputs) is a term in engineering areas and applied mathematics such as process-control and wireless communication. Suppose you have a directed graph ...
1
vote
2answers
41 views

Number of graph vertices of odd degree is even

This elementary result is normally stated as a corollary to the Handshaking Lemma, which says nothing about it other than that it's true. I wonder if there is more depth to this fact, in particular if ...
0
votes
0answers
13 views

Coefficient of Multinomial kind of expression

How do I find the Multinomial coefficient of expression. For example $(x+y+z+w+6)^8$ let say I want the coefficient of xyzw. I know the answer in the simple case of $(x+3)^5$ , for $x^2$ it will ...
0
votes
1answer
40 views

Clique number of the Hajos Construction of a Graph

Prove that $\omega(G)-1 \leq \omega(H(G,v_1,v_2)) \leq \omega(G) $. The $H(G,v1,v2)$ indicates the Hajos Construction of a graph. I can prove this for $K_n$ but I have no idea how to generalize for ...
0
votes
2answers
38 views

Proving the number of leaves of a tree. (Graph Theory)

Prove that if a tree has $n$ vertices (Where $n\geq 2$)and no vertices has degree of $2$, then $T$ has at least $\frac{n+2}{2}$ leaves. Prove by contradiction Suppose that $T$ has less than ...
1
vote
1answer
26 views

Minimum spanning tree of graph? proof by contradiction?

this is not a homework but I need to understand it before my exam tomorrow. How to prove by contradiction that a minimum spanning tree of a graph G is unique if all the edge weights in G are ...
1
vote
1answer
22 views

Connectivity vs clique number of a graph

Is there some known relationship between the connectivity $\kappa(G)$ and the clique number $\omega(G)$ of a graph? Just out of curiosity. In particular, is $\omega(G)$ bounded by some function of ...
1
vote
0answers
20 views

Graph Theory: Graph on torus

Show that one can draw $K_{5}$ , $K_{6}$ , $K_{7}$ on a torus. Torus: a square where opposite sides have been glued. No idea about how to proceed it :/
0
votes
0answers
12 views

what is reachable vertices meaning?

I did not get what is reachable vertex meaning,when i studied Minimum weight perfect matching. According to Hungarian method,the given matrix like below : \begin{matrix} 1 & 0 ...
-1
votes
0answers
25 views

B={A1, A2, A3, … , An} has SDR show that if min|Ai|=k then B has K! SDR .

Assume that A={A1, A2, ... , An} is a family set of finite sets; SDR definition: Let (X1,...,Xn) be a family of subsets of a set A, indexed by the first n natural numbers. (We allow some of the sets ...
0
votes
1answer
18 views

Proving spanning trees contain all pendant edges.

Illustrate and prove that each spanning that each spanning tree of a connected graph G contains all the pendant edges of G. I already know how to illustrate, however can't prove. It says I need to ...
0
votes
0answers
20 views

Every n circuits in R2 field

I've saw this question today, For every n circuits in R2 field that cut each other circle 2 times, the plane will divide into n(n-1)+2 areas. Iv'e tried to solve this by incution but I cant find the ...
106
votes
9answers
15k views

There are apparently $3072$ ways to draw this flower. But why?

This picture was in my friend's math book: Below the picture it says: There are $3072$ ways to draw this flower, starting from the center of the petals, without lifting the pen. I know ...
2
votes
1answer
22 views

Function as an eigenvector for a matrix?

So I am currently going through this paper: Link Here And in section 2.2, it defines $K$ to be a weighted adjacency matrix for a certain rectangular $n$ by $m$ graph, where the weights are all either ...
0
votes
0answers
18 views

How to prove the following facts regarding the matrix

Let $X$ be a connected graph on $n$ vertices and $n$ edges. Let $Q$ be its edge incidence matrix.If $T\subset \{1,2 ,n\}$ with $|T|=n-1$ then $\det (Q[1,2 ,n-1\mid T])=^+_- 1$ if and only if the ...
0
votes
1answer
31 views

code or algorithm for the independent dominant number

dominating set for a graph $G = (V, E)$ is a subset $D$ of $V$ such that every vertex not in $D$ is adjacent to at least one member of $D$. The domination number $γ(G)$ is the number of vertices in a ...
0
votes
0answers
18 views

3 regular graph, 10 vertices, non-adjacent vertices have common neighbour

How can I show the following: in any 3-regular graph with 10 vertices, every pair of non-adjacent vertices, has a common neighbour. I've seen on the internet that there are some very general proofs ...
0
votes
1answer
21 views

Claim: In every graph with at least 2 vertices you can always find 2 vertices with the same degree

This appeared as an excercise in my problem sheet at uni. How can this be true for any graph? Ive added a pic of a graph which fails. I've put the degree above the vertex. I did this on powerpoint- ...
0
votes
1answer
33 views

Is the Wikipedia article about chordal graphs incorrect?

This is the wiki for chordal graphs. It states that "A perfect elimination ordering in a graph is an ordering of the vertices of the graph such that, for each vertex v, v and the neighbors of v that ...
3
votes
1answer
77 views

What is an intuition behind permanent?

I would like to know what is your intuition behind permanent of a matrix. For me, it looks like someone came and saw determinant, deleted permutation sign and voila, we have permanent and it counts ...
0
votes
1answer
35 views

Graph with nine edges and all vertices of degree 3

There is a graph with nine edges and all vertices of degree 3? I don't think that this graph exist, but I don't know how to proof.
0
votes
1answer
37 views

Is this dual transform incidence and order preserving?

I am trying to understand duality explained in the book Computational Geometry Algorithms and Applications, 3rd Ed - de Berg et al. Unfortunately, I have some problem of solving a question in this ...
0
votes
1answer
6 views

Vertex ideal in graphs?

Vertex ideal originates from lattices here. Is there some relationship to relate it to graphs such as series-parallel graphs?
0
votes
0answers
23 views

Counting the number trees in a graph

I'm having trouble to understand how I should count all the possibilities for a graph with some limitation. The qestion is like this : What will be the number of trees on the graph $T=(V,E)$ where ...
1
vote
0answers
32 views

Is there a concept of distance between number of steps needed to move from one step to another?

Let's say that we have a set of rewrite rules: $$AB \mapsto AC, A \mapsto B, B \mapsto A$$ Given the two strings $ABC$ and $BCC$ we know we can rewrite $$ABC \mapsto ACC \mapsto BCC$$ We can ...