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
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
42 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
45 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
37 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
20 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
83 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
19 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 ...
0
votes
1answer
49 views

Is the Petersen Graph k-partite?

I am trying to find the smallest k for which the Petersen graph on 10 vertices is k-partite. I know that is not bipartite by brute force, however I'm not sure how best to tackle for larger k? Is there ...
0
votes
0answers
15 views

Optimal algorithm for finding maximum number of alternating cycles in edge-colored multigraph

I'm having trouble finding any information on this. Suppose you have an edge-colored multigraph $G$ with its edges being of two colors (for example, a given edge can be either black or grey). An ...
0
votes
0answers
20 views

Is There any formula to calculate automorphism with the spesific graph?

I have n complete graph with s nodes. In the picture , I have 4 complete graphs with 4 nodes.(n=s equality is not necessary,they can be different) Is there any formula to calculate the automorphism ...
0
votes
1answer
72 views

eigenvectors for hypercube graphs

Consider a set of size $n$ like $\Omega =\lbrace 1,2,\cdots ,n\rbrace $, where $n$ is a positive integer. For every $x\in P(\Omega )$, define the function $f^x:P(\Omega )\rightarrow \lbrace \pm 1 ...
2
votes
0answers
117 views

basic concept about edge graphs (line graphs)

I was learning about the edge graphs or line graphs $L(G)$ of a graph $G$. I read about the relation between degree of any two vertices $u$ and $v$ in $G$ and that of edge $uv$ in $L(G)$. I am just ...
0
votes
0answers
20 views

Intuition behind spectral radius of a graph

Suppose that I have a graph G, along with its respective adjacency matrix A. The definition of how one can compute the spectral radius of this graph is not hard to grasp, but I was wondering about the ...
0
votes
0answers
17 views

Left-Right planarity Testing for Petersen graph

Could somebody tell me how to use the signed constraint of the left-right planarity criterion to show Petersen graph is not planar?
4
votes
0answers
38 views

Which complete weighted graphs are obtained from finite metric spaces?

Let $(X, d)$ be a finite metric space with $X = \{x_1, \dots, x_n\}$. We can associate to this metric space a complete weighted graph with vertices labelled by the points of $X$, and edges weighted by ...
0
votes
1answer
21 views

projections of a polygonal line

Does there exist a closed nonempty connection of line segments $X$, joined by their endpoints in space so that for every co-ordinate plane, the union of the projections from $X$ to the plane is a ...
0
votes
2answers
55 views

Four color theorem for volume.

Is there a such result for volume in general ? and for space of higher dimension ? What I mean is for example, if you break a brick in many pieces and you restick them again, how many color at most ...
0
votes
1answer
14 views

Exponent of adjacency matrix in a graph

Does the meaning of n-th exponent of adjacency matrix giving us number of walks from some node to other remain, if i have a self-loop, i.e. a node connected to itself?
1
vote
0answers
36 views

On the relations between Graph Theory and Algebra

Below I quote two paragraphs I need your help on. I keep on reading on the mathematical structures of language, where some authors like Zellig Harris come to analogies (and more than analogies) like ...
0
votes
0answers
30 views

How to plot a non-commuting graph?

I'm studying non-commuting graphs in the Erdos problem. Although I'll also study infinity groups, I'd like to add some examples of non-commuting graphs of finite groups, to become more visual . Does ...
0
votes
0answers
21 views

An example of a DFS-oriented graph

Could somebody give an example of a DFS-oriented graph with a non-aligned LR-partition such that the corresponding LR-ordering does not yield a planar embedding?
0
votes
0answers
28 views

Normal subgroup in graph automorphism

Let be $ \Gamma$ a graph, and define $G:=Aut( \Gamma)$. If $N\triangleleft G$, I need to answer if $N$ correspond to a graphical minor of $\Gamma$. I also need to answer the question to $G/N$. I ...
0
votes
1answer
43 views

What is a graph that contains subdivision but not minors and vice versa?

I am looking for graphs which satisfy the following conditions. (I have tried finding some possible solutions but no way to confirm them) (a). a K5 as a minor but no K5-subdivision? ans. Petersen ...
1
vote
2answers
63 views

Walks on a n x n grid

Suppose a person is walking on an n x n grid, starting from the lower, left corner (0,0) walking up to the upper-right corner (n-1, n-1). How many different paths are possible for the person to reach ...
1
vote
0answers
31 views

An exam question about digraph and adjacency matrix

I have an exam question, but I could not understand properly and solve it ;; Using the adjacency matrix V of a digraph G, how do you determine the set of predecessors of a given node u? Determine the ...
0
votes
0answers
21 views

Cartesian product of automorphisms of two graphs

Let be $\Gamma_1$ and $\Gamma_2$ two simple graphs on $n$ vertices. I want to know if there always exists a connected graph $\Gamma$ whose automorphism group is isomorphic to $ Aut(\Gamma_1)\times ...
0
votes
1answer
18 views

Semi Eulerian graphs

I do not understand how it is possible to for a graph to be semi-Eulerian. For a graph G to be Eulerian, it must be connected and every vertex must have even degree. If something is semi-Eulerian ...
0
votes
1answer
31 views

Showing CP-rule is not optimal for $P \mid p_j = 1, \text{ intree} \mid \sum C_j$.

We are asked to find a counterexample that shows that the Critical Path rule is not optimal for $P \mid p_j = 1, \text{ intree} \mid \sum C_j$. However, after trying for two hours, I don't think I'll ...
0
votes
1answer
28 views

An example for a planar graph with different embeddings with different degree sequences of the faces?

Let $G$ be a planar graph with a planar embedding with $f$ faces. The degree of a face $f_i$ is the number $a_i$ of edges that are incident to $f_i$ (counting bridges twice). Assume that the faces ...
0
votes
0answers
23 views

Graph Centrality: spectral techniques

What is the difference between: normalizing the row of an adjacency matrix and taking the right eigenvector normalizing the row of an adjacency matrix and taking the left eigenvector ...
1
vote
1answer
61 views

Bounding the edges belonging to no perfect matching

We are told to let $G = (X \cup Y, E)$ be a bipartite graph with $|X|=|Y|=n$, and to suppose that $G$ has a perfect matching. I am trying to find a way to prove that $G$ has at most $n \choose 2$ ...
1
vote
0answers
15 views

Simplicial Complexes of Graphs notation question

I'm studying Jakob Jonsson's book Simplicial Complexes of Graphs very rigorously and in depth. I've been okay so far with the intensity and notation, but on page Chapter 3, section 2, page 30, I'm ...
-1
votes
0answers
14 views

Prove that Breadth First Search is the “shortest path tree”.

Prove that Breadth First Search is the "shortest path tree". I defined the shortest path tree as exhibiting all the shortest paths from the roots to all other vertices. My class is using BFS in a ...
-2
votes
0answers
17 views

Prove when Breadth First Search is applied, the endpoints of each nontree edge are either at the same level or a

Prove when Breadth First Search is applied, the endpoints of each nontree edge are either at the same level or at consecutive levels of the resulting tree. My class is using BFS in a non-computer ...