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

Simplification of an expression sums and products

I am trying to simply the following expression: $ \sum_{\substack{\overline{t}_i , \overline{t}_j \in \{H,L\} \\ \forall j \in N_i}}^{} \sum_{j \in N_i}^{} \alpha_{\overline{t}_i , \overline{t}_{j}} ...
0
votes
1answer
19 views

Turan-related graph theory question

Let us have a $G$ graph, which has $4$ vertices and $4$ edges, and $3$ vertices create a triangle. What is the value of $ex(n,G)$ for all $n$? So basically the task is: If I have $n$ vertices, what ...
0
votes
1answer
19 views

What is the special of product of the incidence matrix and its transpose for an undirected graph

Can some one tell me what is the special of product of the incidence matrix and its transpose for an undirected graph ?. I try get product of a incidence matrix and its transpose for an undirected ...
2
votes
1answer
70 views

Pairing Vertices by Edge Color

We have a graph $G$ with an even number of vertices. Every pair of vertices is connected by either a green or red edge. If every vertex is connected to at least one other vertex by a green edge, can ...
0
votes
0answers
18 views

Term for a graph with input and output ports

A Graph is a well-defined concept in mathematics, computer science and engineering disciplines that depend on them. However, oftentimes a practical implementation of a (directed) graph in a certain ...
1
vote
0answers
10 views

graph has no bridge iff a spanning subgraph of the graph is the support of a flow

A $\textit{bridge}$ of a graph $G=(V,E)$ (finite graph and we allow loops and multiple edges) is an edge $e$ whose removal disconnects $G$. Let $\mathcal{O}$ be an orientation of the edges of $G$. ...
0
votes
0answers
44 views

Prove that every connected graph whose vertices are all of even degree has no cut-vertices

I am trying to prove that every connected graph whose vertices are all of even degree has no cut-vertices. Now, I am not very good with proofs but I was thinking about proving it by contradiction, ...
1
vote
1answer
31 views

Is there any relation between these matrices?

$Q$ is $(0,1,-1)$ vertex edge incidence matrix of a simple directed graph. $M$ is $(0,1)$ vertex edge incidence matrix of a simple non directed graph. $A$ is vertex vertex incidence matrix of a graph. ...
0
votes
1answer
31 views

Electrical Resistance between end points of a square grid is maximum using graph theory

Let $G$ be a $n\times n$ square grid with a $1 \Omega$ resistor on each edge. Why is the resistance between the $(0,0)$ and $(n,n)$ the lowest( Previously was highest)? I am interested in the general ...
0
votes
1answer
20 views

Edge intersections of paths

I am trying to read up on the nonrepetitive graph coloring problem. That's for context, my question can be answered without referring to the problem. I have a graph G, and I am interested in looking ...
0
votes
1answer
25 views

Directed spanning tree

Consider a directed graph. Is there any theorem on minimum number of outgoing or incoming links for each node of digraph that guarantees the existence of directed spanning tree?
0
votes
0answers
14 views

The smallest value of the Laplacian of a subdivided graph

Given a graph $G$, the normalized Laplacian $\Delta$ acts on the real-valued space of functions on the vertices of $G$ by $$\Delta f(v) = f(v) - \frac{1}{m(v)}\sum_{u - v} f(u)$$ where $m(v)$ is the ...
0
votes
1answer
25 views

Trying to find the markov chain and adjacency matrix of this graph?

This is graph of the problem: Suppose animal x is at node 3 of the graph. It chooses small path labelled s with 2 times probability then long path l. If length is same then probability is same ...
1
vote
0answers
20 views

Is modularity of -1 possible

Wikipedia mentions that modularity of a network is within the range [-1,1).But if we consider a complete graph with n nodes and assign different community to each node than the modularity turns out to ...
1
vote
2answers
56 views

Shortest Path on Specific Graph with one Property !?

I stuck in one challenging question, I read on my notes. An undirected, weighted, connected graph $G$, (with no negative weights and with all weights distinct) is given. We know that, in this ...
1
vote
1answer
21 views

A clique in a tree decomposition is contained in a bag

Let $G$ be a graph, $T$ a tree and $\mathcal{V}=\bigcup_{t \in T} V_t$ a tree decomposition of $G$. Let $H \leq G$ be a clique. Show that $H$ is contained in a bag $V_t$ for some vertex $t \in T$. ...
0
votes
1answer
28 views

Question on the proof of the upper bound of girth in dense graph.

I have trouble understanding the proof of the following theorem from Upfal's Probability textbook pg 134 Theorem: For any integer $k \geq 3$ there is a graph with n nodes, at least ...
0
votes
0answers
19 views

Integral weighted graphs

I found some useful guidelines to investigate integral graphs (i.e. that the eigenvalues of the adjacency matrix are all integers) http://link.springer.com/chapter/10.1007%2FBFb0066434 . However, ...
1
vote
2answers
27 views

Proving isomorphism between graphs

If I'm asked to prove two graphs are isomorphic by constructing an isomorphism E.g for these two graphs if I start from $u_1$ I have an option to send $u_1$ to any of $v_1$ to $v_6$ and I start by ...
1
vote
0answers
21 views

Embedding of $K_{2,3}$ into $\ell_1$

I am looking for hints for the following problem: Prove that every embedding of $K_{2,3}$ (with the shortest path metric and unit edge-length) into $\ell_1$ has distortion at least 4/3! Notation: ...
0
votes
1answer
14 views

A graph that all its vertices are vertices cut [duplicate]

Is there any graph that all its vertices are cut vertices? I couldn't find a graph with this property? and if there is no such graph how can i prove that it does not exist.
-2
votes
0answers
19 views

Finding maximally weighted subgraph triangles from a complete graph.

In a Complete Graph of say, $|V| = 12$, where the edges are all weighted, how can you select $4$ triangles of $3$ vertices and $3$ edges (disjoint subgraphs), such that the triangles are maximally ...
0
votes
0answers
10 views

Hajos construction on C4

I've been asked to prove that χ(H(G, v1, v2)) = χ(G) where H(G,v1,v2) is the Hajós construction of G. However, if I understand the Hajós construction as it's described on wikipedia, then H(C4,v1,v2) ...
0
votes
1answer
38 views

graph theory δ(G) + δ(complement G) <= n - 1

Hi I am new to graph theory and being terrible with proofs I am looking for some hints to prove this: Prove that if G is a graph of order n, then δ(G) + δ(complement of G) ≤ n − 1. I know that ...
0
votes
1answer
25 views

Birkhoff's definition of semilattice?

could anyone provide me with the original definition of semilattice by Garrett Birkhoff in his book on lattices? If you could also provide, page number and edition, it would be great (as well as some ...
1
vote
1answer
29 views

prove $G-e$ is $(k-1)$-edge connected.

if G is $k$-edge-connected graph and $e$ is an edge of $G$, prove that $G-e$ is $(k-1)$-edge-connected? Could someone help me this question? My thought is suppose there is a set $E$ of $k-2$ edges ...
0
votes
1answer
34 views

Get degree distribution of a graph from its Adjacency matrix

How can you get the degree distribution of a graph from the following formulas, and also determine if those graphs are directed or not ? : where $\delta$ represents the Kronecker delta a) $A_{ij} = ...
1
vote
0answers
11 views

amenable groups versus amenable graphs

In operator algebras, one is often concerned with amenable groups, defined by one of many equivalent conditions. http://en.wikipedia.org/wiki/Amenable_group#Equivalent_conditions_for_amenability In ...
0
votes
1answer
41 views

left and right multiplication for Cayley graphs

Correct me if i am wrong but i have written down the following: If $X$ is a finite group, with subset $S$ and corresponding Cayley graph $G$ The edge set for a Cayley graph is defined such that two ...
2
votes
3answers
45 views

Clear up definition of cayley graph

I have come across two definitions of Cayley graphs, both very similar but one being more general. I have been working with the more general definition which is: A Cayley graph of a group 􏰎$X$ ...
3
votes
0answers
35 views

Forming the graph $G$ from elements of the cut and cycle space, using a weird hint

I'm working through a set of lecture notes on my own, and since there is no class, there are no immediate faculty members available to ask questions to. I've managed to finish most exercises quite ...
0
votes
1answer
17 views

On Dynkin diagramms and Graph Theory

I would like to know whether there are some obvious relation between Dynkin Diagramms and Graph Theory in its more general formulation, and, if so, I am particularly interested in knowing: 1) whether ...
2
votes
1answer
37 views

Longest Path in undirected unweighted graph

I came across a problem where I have to find out the longest path in a given graph. I have list of edges ( eg.{AB, BC} ) which states there is an edge between vertices/nodes (A,B,C). Now i want to ...
1
vote
2answers
36 views

Let G be a simple graph of order $n\geq 2$. If $|E(G)|>\binom{n-1}{2}$,then G is connected.

Let G be a simple graph of order $n\geq 2$. If $|E(G)|>\binom{n-1}{2}$,then G is connected. One of the solution I get is as shown as below: Suppose G is not connected, Then G is a disjoint union ...
-2
votes
0answers
10 views

Minors of Eulerian graphs

Under what conditions in the minor of an Eulerian graph Eulerian? ...
1
vote
1answer
40 views

Is there accepted name for digraph segement without “joins” or “turns”?

As example lets consider following directed graph: ...
0
votes
2answers
36 views

Finding the minimum wins in a round-robin tournament.

There are 16 teams in total. They are divided into two groups of 8 each. In a group, each team plays a single match against every other team. At the end of the round, top 4 teams go through to the ...
1
vote
2answers
19 views

Why is the maximum cut of an undirected graph at lest 1/2 the number of edges in the graph?

In Upfal's Probability textbook he claims in Theorem 6.3 Given an undirected graph G with n vertices and m edges there is a partition of V into two disjoint sets A and B such that at least m/2 edges ...
0
votes
0answers
13 views

Arguing independent set [duplicate]

Let $G = (V, E)$ be a graph with vertex set $V$ and edge set $E$. A subset $I$ of $V$ is called an independent set if for any two distinct vertices $u$ and $v$ in $I$, $(u, v)$ is not an edge in $E$. ...
0
votes
1answer
50 views

Probability proof and graphs

Let $G = (V, E)$ be a graph with vertex set $V$ and edge set $E$. A subset $I$ of $V$ is called an independent set if for any two distinct vertices $u$ and $v$ in $I$, $(u, v)$ is not an edge in $E$. ...
0
votes
0answers
82 views

Edge and Vertex set proof using an algorithm

Disclaimer: This is a homework question, so no direct answers please. All that I'm looking for is a good springboard to get started from with this question, as it has been tearing me apart for the ...
0
votes
0answers
28 views

Are all Regular Graphs Simple?

Sorry if this is a dumb question, but is it always assumed that regular graphs are always simple? Or is this too presumptuous? Thanks!
0
votes
1answer
32 views

Determining the number of vertices of each degree

Question: Let G be a simple graph with 6 vertices and 10 edges such that every vertex of G has an odd degree. If the number of vertices of degree 3 is one more that the number of vertices of degree 5, ...
0
votes
0answers
19 views

Graph theory problem where squares in a square are shaded such that no shaded square can be on the same 'lane' as another shaded square

I came across a question on the internet and haven't been able to find it again. Maximum number of shaded squares in a larger square (all smaller squares are of the same size) such that no two squares ...
5
votes
1answer
81 views

Is it true that a graph with many edges has a long route?

Is the following sentence true or not? If we have a graph with $n$ vertices, and $e$ edges, if $e > 100 n$, then we always have a $100$-long route in the graph. I think it is true, I tried to use ...
0
votes
1answer
33 views

Proof that $\lambda(G) = \kappa(G)$

Let $\lambda(G)$ be edge connectivity of graph and $\kappa(G)$ vertex connectivity. How can I proof that $\lambda(G) = \kappa(G)$ for every graph where every vertex of this graph has degree not ...
0
votes
1answer
18 views

Edge connectivity in graph

Let $\lambda(G)$ be edge connectivity. Can anyone help me with those two statements if they are true and if so then why? $$ \lambda(G) \geq \lambda(G - e) $$ $$ \lambda(G - v) \geq \lambda(G) - 1 ...
0
votes
0answers
23 views

Incomparable Graphs

Two undirected graphs $G$ and $H$ are incomparable if $G\not\leftrightarrow H$, i.e. there is no homomorphism from $G$ to $H$ and none from $H$ to $G$. Are there properties of $G$ and $H$ or anything ...
0
votes
0answers
15 views

Szemerédi's Degree Regularity Lemma

Does anyone know where I can find a nice clean proof of the Szemerédi's Degree Regularity Lemma that is similar to follow of the original Szemerédi's Regularity Lemma that is not a PDF of hundreds of ...
1
vote
0answers
11 views

The correctness of fast chung-lu model

This paper (fast generation of large scale social networks with clustering) mentioned in its proposition 1 that "in a regular graph, the probability of an edge existing in the fast Chung Lu model is ...