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...

We prove that, for any prime $p$, there are precisely $2p^4-p^3-p^2-3p-1$ medial quasigroups of order $p^2$, up to isomorphism.

Our aim is to demonstrate how the apparatus of groupoid terms (on two variables) might be employed for studying properties of parallelism in the so called $(n,k)$-quasigroups. We show that an incidence structure associated with a medial quasigroup of type $(n,k)$, $n>k\ge 3$, is either an affine space of dimension at least three, or a desarguesian plane. Conversely, if we start either with an affine space of order $k>2$ and dimension $m$, or with a desarguesian affine plane of order $k>2$ then there is a medial quasigroup of...

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.