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

4
votes
2answers
73 views

Prove that a graph which is constructed with matrices is strongly regular

Suppose that $F_q$ is a field with $q$ elements. Consider all $2\times d$ matrices with entries in $F_q$, so we have $q^{2d}$ matrices. Consider each matrix as a vertex, and two vertices $A$ and $B$ ...
2
votes
2answers
113 views

$G^k$ is k-connected - different approach for proof

Question: For a connected graph $G = (V, E)$ and a positive integer $k$, let $G^k$ be the graph with vertex set $V$ , where two vertices are connected by an edge if and only if their distance in $G$ ...
3
votes
0answers
70 views

Structural / design / meta optimization - is there mathematical theory. Optimization over categories?

There is huge branch of mathematical optimization theory, but it mostly considers the finding optimal parameter values for the predefined structures. There are variational calculus and optimal control ...
4
votes
1answer
86 views

Composer's dilema - Graph Theory

I am a composer. I have 10, 30-second musical sections. The orchestra plays 5, five are played by a soloist. I would like to give them each choices. I have written the piece so that each section flows ...
3
votes
1answer
59 views

How many matroids with 1 element exist?

So we got the following question in the lecture: How many matroids with a single element exist? Couldn't really think of an answer. Any assistance would be of help!
3
votes
1answer
59 views

Mathematical name of this type of graph

If you have a tree that also might merge branches, but only in a directed way, i.e. all edges are one step either towards or away from the "root", what can we call it? It's a special case of a ...
0
votes
2answers
79 views

The equality $\chi(G-v)=\chi(G)$

Let $G$ be a graph and $\deg(v)<\chi(G)-1$. By $\deg(v)$ and $\chi(G)$, I mean the degree of vertex $v$ and chromatic number of the graph $G$, respectively. I want to show that $\chi(G-v)=\chi(G)$.
2
votes
0answers
38 views

Spectral radius of a time-varying matrix with strictly positive increment

Consider a time varying non-negative matrix $A(t)$ and its spectral radius $\rho(A(t))$ where $t$ denotes the time. If $A(t)$ changes over time with each time a random element in $A(t)$ is being ...
2
votes
2answers
78 views

An identity that comes from computing the Wiener index of a cyclic graph

Can the below identity be proven in such a way that we can generalize it? $(1 + 1 + 2 + 2 + 3 + 3 + 4) +( 1 + 2 + 2 + 3 + 3 + 4) + (1 + 2 + 3 + 3 + 4)+ +( 1 + 2 + 3 + 4 )+(1 + 2 + 3) + (1 + 2) + 1 = {...
3
votes
1answer
73 views

$G^k$ is $k$-connected

For a connected graph $G$ on $n$ vertices and $1\le k \le n-1$ prove that the graph $G^k$ (where two vertices are connected if their distance is at most $k$) is $k$(-vertex)-connected. We need to ...
0
votes
2answers
79 views

What is the probability of a chain of a given length in a random graph?

Let $G$ be an undirected graph with $n$ nodes. An edge is randomly and independently drawn from each node to any of the other nodes. If some arbitrary node $a$ is chosen, what is the probability that ...
0
votes
1answer
66 views

number of ways to label in a cycle

Suppose I have a 6 vertices complete graph, Say it G. It is labeled, Now I need to find all distinct 4 vertices cycles. So for first step there are 6C4 ways to select 4 length cycles , but as it is ...
0
votes
0answers
574 views

number of distinct simple graphs with n vertices?

To calculate simple, labelled graphs is easy with the formula $2^{n(n-1)/2}$, but if we say distinct, then it would certainly be less than it, because some possible situations will be same hence not ...
2
votes
1answer
109 views

How to test that this 3D graph is rigid?

I have constructed a lattice as a 3D graph while ensuring that it is rigid. I would like to find a way to test it to verify. Any thoughts? Links to papers?
0
votes
1answer
65 views

How many $k$-regular bipartite graphs can I make given $n$ distinct vertices?

I'm attempting to solve a problem that I think can be solved best with graph theory. I know very little regarding graph theory, so excuse any misuse of vocabulary (which I only picked up in the last ...
4
votes
1answer
112 views

parity bias for trees?

Let $t(n)$ denote the number of unlabeled unrooted trees on n vertices, e.g. $t(4)=2$ . Next denote by $\operatorname{even}(n)$ the number of such trees having an even number of endpoints. Similarly, ...
3
votes
1answer
76 views

Is this random binary tree finite?

Consider the following procedure for generating a random binary tree: Starting with a full binary tree (i.e., each node has either two or no children) we iterate over the leaves and (independently) ...
1
vote
0answers
59 views

Expected Max Pseudotree Size

I'm working on a problem where I need to calculate the expected maximum pseudotree size in a randomly-generated pseudoforest with $n$ nodes. Expected maximum value is of course: $$ E(x) = \sum_{i=1}^...
0
votes
1answer
795 views

Fundamental circuit and cut-set [closed]

When Finding all the fundamental circuits and cut sets of $K_{3,3}$ and $K_5$ graph ,does planarity have any effect ?
2
votes
1answer
142 views

What is the smallest and the largest possible adjacency eigenvalue of a regular graph?

For a $d-$regular graph I think $d$ is always the largest adjacency eigenvalue and if its bipartite then I think $-d$ is the smallest possible.
0
votes
1answer
59 views

What is the solution to this graph question? [duplicate]

Hi everybody, is there anybody who can answer the following problem? I dont know how to start solving it, thank you very much.![the question is in the picture below][2]
1
vote
2answers
427 views

Tree with radius and diameter

How to show that a radius in a tree is not necessarily half its diameter ?? I'm using the following relation to prove but cannot find proper explanation 2*radius-1 ≤ diameter ≤ 2*radius Suggest if ...
2
votes
0answers
89 views

Checking if a relation is complete

I have a transitive relation $\subset$ on a (finite and small) set S and a list of pairs $x_i\subset y_i.$ I would like to check if my list is complete in the sense that if $x\subset y$ then there are ...
1
vote
1answer
69 views

suppose $G$ is strongly regular graph srg$(n,k,\lambda,\mu)$,prove that $k\geq 2\lambda -\mu +3 $.

suppose $G$ is strongly regular graph srg$(n,k,\lambda,\mu)$,prove that $k\geq 2\lambda -\mu +3 $. I tried to show that $\mu(n-1)\geq k(\lambda+2)$(*) if I can prove that,then I add $-\mu k$ to both ...
4
votes
1answer
356 views

What does this definition of an $H$-path mean?

I'm going through a graph theory book, which defines an $H$-path as follows: Given a graph $H$, we call $P$ an $H$-path if $P$ is non-trivial and meets $H$ exactly in its ends. In particular, the ...
6
votes
1answer
197 views

suppose $n$ people are in a party and every two of them have exactly one common friends,prove that there is one who is friend to all.

suppose $n$ people are in a party and every two of them have exactly one common friends,prove that there is one who is friend to all. I suppose there is no one who is friend to all,I want to show ...
0
votes
0answers
35 views

Finding all planar graphs with more regions than edges.

I want to find all planar graphs with more regions than edges. This is my solution. Let $G=(V,E)$ be a planar graph and pick a planar representation. If $G$ is connected, I can use Euler's formula. ...
0
votes
1answer
40 views

List (of) all cubic planar graph with 30 vertices

Where can I find the list of all possible cubic planar graphs (without triangles) having 30 vertices? Are there online databases for that?
1
vote
1answer
35 views

give an example to show it is possible to remove one vertex and the multiplicity of one of eigenvalue rise.

I know that if we consider a graph $G$ with $\lambda$ as one of its eigenvalue of adjacency matrix with multiplicity $n$ ,there is a vertex of $G$ that by removing it ,the multiplicity of $\lambda$ ...
1
vote
2answers
67 views

Two finite graphs with n vertices: Can one have both more components and more edges than the other?

Suppose $G$ and $G'$ are two graphs having $n$ vertices.For what values of $n$ is it possible for $G$ to have more components and edges than $G'$? What could be the possible values of $n$?
2
votes
1answer
77 views

What is the relation between linear subgraph and matching polynomial?

I am confused about these following three concepts, An edge-cycle subgraph of a graph $G$ (also called a linear subgraph of $G$) is a subgraph of $G$ whose components are cycles and edges. A set of ...
10
votes
1answer
2k views

Powers of adjacency matrix doesn't seem to correspond to observed number of paths on graph

I would really appreciate some help on this! $A^n$ represents $n^{th}$ power of the adjacency matrix of a graph. I keep reading that the $A^n_{ij}$ entry equals "the number of paths of length n ...
1
vote
3answers
110 views

Is there a 5-regular graph of order 7?

How can I decide if there is a 5-regular graph of order 7? Some hints or tips would be appreciated. This question arises in studying for a graph theory course.
0
votes
1answer
63 views

Is there any regular polyhedron that is not of Euler characteristic 2

Is there any regular polyhedron that 1. consist of congruent regular polygons as its faces 2. each vertex has same number of adjacent edges but nonetheless not of characteristic 2? (say, torus or ...
0
votes
2answers
59 views

Calculating interaction beween 100 objects with each other.

The other day I was thinking about how many interactions 100 objects would have with each other. By that I mean if we are using a computer to draw the scene with 100 point lights, the total result ...
1
vote
2answers
322 views

Prove: Graph in which every pair of vertices has an odd number of common neighbors is Eulerian.

Let $G$ be a graph in which every pair of vertices has an odd number of common neighbors. Prove that $G$ is Eulerian. I have in mind two main ways to prove this but every time I get stuck. Get a ...
0
votes
1answer
71 views

Graph theory and tree company

I appreciate anyone who answer this question and I anyone who design appropriate graph.
0
votes
1answer
49 views

suppose a graph $G$ is 3-regular with bridge (cut edge),do we have $\chi^{'}(G)=4$?

suppose a graph $G$ is 3-regular with bridge (cut edge),do we have $\chi^{'}(G)=4$? I think that it is right but I couldn't prove it,can you give me some hint or guidance about it,thanks a lot.
0
votes
1answer
123 views

Existence of a maximum matching containing a vertex $v$ in a graph

Let $v$ be a vertex of a graph $G$, which is not isolated. Prove the existence of a maximum matching in which $v$ is saturated (matched).
1
vote
1answer
24 views

an example for an arbitrary graph $G$ with even vertices which $\forall S \in V(G) , |N(S)|\geq |S| $ but there is no complete matching .

I want to say an example for an arbitrary graph $G$ with even vertices which $\forall S \in V(G) , |N(S)|\geq |S| $ but there is no complete matching . I have tried so many shapes but I couldn't ...
6
votes
2answers
3k views

Number of edges in a graph with n vertices and k connected components

Let $m$ be te number of edges, $n$ the number of vertices and $k$ the number of connected components of a graph G. Prove that: $m$ $\leq$ $\frac{(n-k+1)*(n-k)}{2}$ Thanks!
1
vote
0answers
47 views

Deviation of number of cycles of length 4 in Erdős–Rényi random graphs.

I'm working on my homework and can't find any relevant information for this problem. Problem: Let $G(n, p)$ be Erdős–Rényi random graph. I need to find deviation of number of cycles of length 4 in ...
1
vote
1answer
71 views

Triangles formed by line segments in a square

There is a square, denoted by points A, B, C, and D. There are 30 distinct points located inside the square (call these $A_2, A_3, A_4, ... A_{31}$. Non-intersecting segments $A_iA_j$ vertices are ...
4
votes
4answers
366 views

Triangle-free graph with 5 vertices

What is the maximum number of edges in a triangle-free graph on 5 vertices? No answers, please...just hints. I believe that E $\leq$ 5, but I'm not sure where to go from there.
5
votes
1answer
193 views

all possible values of vertices, given the number of faces and all the vertices have the same degree on a connected planar graph?

A connected planar graph has 26 faces and an unknown amount of vertices (denoted as "V"). All the vertices have the same degree. What are all possible values of V? What I have so far: V + F = E + ...
0
votes
1answer
369 views

Check if Sequence is Graphic: 8, 8, 7, 7, 6, 6, 4, 3, 2, 1, 1, 1 [duplicate]

This is part of my Discrete Math homework and I have no idea how to solve this. I am given this sequence: $8, 8, 7, 7, 6, 6, 4, 3, 2, 1, 1, 1 $ I have to check whether it is graphic or not. How do ...
3
votes
0answers
104 views

a problem about finding an algorithm for a spanning tree in a 3-regular graph

"Consider the connected 3-regular graph G. Find an algorithm that produces a subgraph S of G which is a spanning tree and if you remove S from G then G is divided into some components that each of ...
2
votes
1answer
84 views

What is $\tau(A)$ of components of $G \backslash A$, where $A \subseteq V$?

A graph is $t$-tough if for all cutsets $A$ we have : definition of t-tough can be found here http://personal.stevens.edu/~dbauer/pdf/dmn04f6.pdf Now I am reading a paper which author defines t-...
1
vote
3answers
176 views

How many ways to make a connected graph using 4, 5, 6 edges?

How can/how many ways can you make a connected graph that has 5 vertices using 4, 5, 6 edges? I'm not sure how it would look like for 4 edges. Can you draw a diagram?
1
vote
0answers
57 views

Inequality to bound $\sum_i a_i b_i - \sum_i c_i d_i$ (harmonic eigenfunction/graph) type sum with constraints

We have a homogeneous graph $G = (V,E)$ with a function $f:V\rightarrow \mathbb{R}$. We define the following modulus: $\displaystyle \omega(s) = \sup\{f(x)-f(y) \ | \ |x-y|=s \}$ and wish to lower ...