An (f, g)-semi-matching in a bipartite graph G = (U ∪ V,E) is a set of edges M ⊆ E such that each vertex u ∈ U is incident with at most f(u) edges of M, and each vertex v ∈ V is incident with at most g(v) edges of M. In this paper we give an algorithm that for a graph with n vertices and m edges, n ≤ m, constructs a maximum (f, g)-semi-matching in running time O(m ⋅ min [...] ) Using the reduction of [5] our result on maximum (f, g)-semi-matching problem directly implies an algorithm for the optimal...

The mean value of the matching polynomial is computed in the family of all labeled graphs with n vertices. We introduce the dominating polynomial of a graph whose coefficients enumerate the dominating sets for a graph and study some properties of the polynomial. The mean value of this polynomial is determined in a certain special family of bipartite digraphs.

For a connected graph $G$ of order $n\ge 3$ and an ordering $s{v}_1$, $v_2,\cdots ,v_n$ of the vertices of $G$, $d\left(s\right)={\sum }_{i=1}^{n-1}d(v_i,v_{i+1})$, where $d(v_i,v_{i+1})$ is the distance between $v_i$ and $v_{i+1}$. The traceable number $t\left(G\right)$ of $G$ is defined by $t\left(G\right)=min\left\}d\left(s\right)\right\{,$ where the minimum is taken over all sequences $s$ of the elements of $V\left(G\right)$. It is shown that if $G$ is a nontrivial connected graph of order $n$ such that $l$ is the length of a longest path in $G$ and $p$ is the maximum size of a spanning linear forest in $G$, then $2n-2-p\le t\left(G\right)\le 2n-2-l$ and both these bounds are sharp. We establish a formula for the traceable number of...

We consider the problem of finding a measurable unfriendly partition of the vertex set of a locally finite Borel graph on standard probability space. After isolating a sufficient condition for the existence of such a partition, we show how it settles the dynamical analog of the problem (up to weak equivalence) for graphs induced by free, measure-preserving actions of groups with designated finite generating set. As a corollary, we obtain the existence of translation-invariant random unfriendly colorings...

Median graphs are characterized among direct products of graphs on at least three vertices. Beside some trivial cases, it is shown that one component of G×P₃ is median if and only if G is a tree in that the distance between any two vertices of degree at least 3 is even. In addition, some partial results considering median graphs of the form G×K₂ are proved, and it is shown that the only nonbipartite quasi-median direct product is K₃×K₃.

For any vertex v and any edge e in a non-trivial connected graph G, the distance sum d(v) of v is $d\left(v\right)={\sum }_{u\in V}d(v,u)$, the vertex-to-edge distance sum d₁(v) of v is $d₁\left(v\right)={\sum }_{e\in E}d(v,e)$, the edge-to-vertex distance sum d₂(e) of e is $d₂\left(e\right)={\sum }_{v\in V}d(e,v)$ and the edge-to-edge distance sum d₃(e) of e is $d₃\left(e\right)={\sum }_{f\in E}d(e,f)$. The set M(G) of all vertices v for which d(v) is minimum is the median of G; the set M₁(G) of all vertices v for which d₁(v) is minimum is the vertex-to-edge median of G; the set M₂(G) of all edges e for which d₂(e) is minimum is the edge-to-vertex median...

Two numerical invariants $\Delta \left(G\right)$ and $\Gamma \left(G\right)$ of a graph, related to the concept of median, are studied.

Après quelques considérations générales sur les relations entre les mathématiques discrètes, l'informatique et l'analyse des données, ce texte présente un ensemble de méthodes utilisant des techniques ordinales ou (et) combinatoires. A une description succinte de chaque méthode sont jointes quelques références relatives à ses aspects théoriques ainsi qu'à ses implémentations accessibles aux utilisateurs. Pour présenter ces méthodes nous les avons classées suivant la nature des tableaux de données...

We show that superreflexivity can be characterized in terms of bilipschitz embeddability of word hyperbolic groups.We compare characterizations of superrefiexivity in terms of diamond graphs and binary trees.We show that there exist sequences of series-parallel graphs of increasing topological complexitywhich admit uniformly bilipschitz embeddings into a Hilbert space, and thus do not characterize superrefiexivity.