This is an extended version of a talk given by the author at the conference “Algebra and Topology in Interaction” on the occasion of the 70th Anniversary of D.B. Fuchs at UC Davis in September 2009. It is a brief survey of an area originated around 1995 by I. Gelfand and the speaker.

A form-finding problem for tensegrity structures is studied; given an abstract graph, we show an algorithm to provide a necessary condition for it to be the underlying graph of a tensegrity in Rd (typically d=2,3) with vertices in general position. Furthermore, for a certain class of graphs our algorithm allows to obtain necessary and sufficient conditions on the relative position of the vertices in order to underlie a tensegrity, for what we propose both a geometric and a symbolic approach.

Starting from the famous Königsberg bridge problem which Euler described in 1736, we intend to show that some results obtained 180 years later by König are very close to Euler's discoveries.

To every graph (or digraph) A, there is an associated automorphism group Aut(A). Frucht’s theorem asserts the converse association; that for any finite group G there is a graph (or digraph) A for which Aut(A) ∼= G. A new operation on digraphs was introduced recently as an aid in solving certain questions regarding cancellation over the direct product of digraphs. Given a digraph A, its factorial A! is certain digraph whose vertex set is the permutations of V (A). The arc set E(A!) forms a group,...

Dado un grafo G = (X,E) con un solo vértice insaturado p, se estudia el problema de encontrar, para todo x ∈ X, un camino M-alternado par que una x con p. Se halla un algoritmo, y se plantea su aplicación cara a dar una variante del Algoritmo de Edmonds en la que no haya que contraer los pseudovértices.

For each vertex v in a graph G, let there be associated a subgraph $H_v$ of G. The vertex v is said to dominate $H_v$ as well as dominate each vertex and edge of $H_v$. A set S of vertices of G is called a full dominating set if every vertex of G is dominated by some vertex of S, as is every edge of G. The minimum cardinality of a full dominating set of G is its full domination number ${\gamma }_{FH}\left(G\right)$. A full dominating set of G of cardinality ${\gamma }_{FH}\left(G\right)$ is called a ${\gamma }_{FH}$-set of G. We study three types of full domination in graphs: full...

Let $G_1$ and $G_2$ be copies of a graph $G$, and let $f:V\left(G_1\right)\to V\left(G_2\right)$ be a function. Then a functigraph $C(G,f)=(V,E)$ is a generalization of a permutation graph, where $V=V\left(G_1\right)\cup V\left(G_2\right)$ and $E=E\left(G_1\right)\cup E\left(G_2\right)\cup \{uv:u\in V\left(G_1\right),v\in V\left(G_2\right),v=f\left(u\right)\}$. In this paper, we study colorability and planarity of functigraphs.

In this note we consider a discrete symmetric function f(x, y) where $$f(x,a)+f(y,b)⩾f(y,a)+f(x,b)foranyx⩾yanda⩾b,$$ associated with the degrees of adjacent vertices in a tree. The extremal trees with respect to the corresponding graph invariant, defined as $$\sum _{uv\in E\left(T\right)}f\left(deg\right(u),deg(v\left)\right),$$ are characterized by the “greedy tree” and “alternating greedy tree”. This is achieved through simple generalizations of previously used ideas on similar questions. As special cases, the already known extremal structures of the Randic index follow as corollaries. The extremal structures...

We introduce the notion of fundamental groupoid of a digraph and prove its basic properties. In particular, we obtain a product theorem and an analogue of the Van Kampen theorem. Considering the category of (undirected) graphs as the full subcategory of digraphs, we transfer the results to the category of graphs. As a corollary we obtain the corresponding results for the fundamental groups of digraphs and graphs. We give an application to graph coloring.

In a graph G, the distance d(u,v) between a pair of vertices u and v is the length of a shortest path joining them. The eccentricity e(u) of a vertex u is the distance to a vertex farthest from u. The minimum eccentricity is called the radius of the graph and the maximum eccentricity is called the diameter of the graph. The radial graph R(G) based on G has the vertex set as in G, two vertices u and v are adjacent in R(G) if the distance between them in G is equal to the radius of G. If G is disconnected,...

Given a graph G with p vertices, q edges and a positive integer k, a k-sequentially additive labeling of G is an assignment of distinct numbers k,k+1,k+2,...,k+p+q-1 to the p+q elements of G so that every edge uv of G receives the sum of the numbers assigned to the vertices u and v. A graph which admits such an assignment to its elements is called a k-sequentially additive graph. In this paper, we give an upper bound for k with respect to which the given graph may possibly be k-sequentially additive...

We describe a correspondence between ${\text{GL}}_n$-invariant tensors and graphs. We then show how this correspondence accommodates various types of symmetries and orientations.