Papers by Riste Škrekovski
Electronic Journal of Combinatorics, Jan 10, 2003
Bookmarks Related papers MentionsView impact
Journal of Graph Theory, 2006
Bookmarks Related papers MentionsView impact
Electronic Notes in Discrete Mathematics, Nov 1, 2001
ABSTRACT
Bookmarks Related papers MentionsView impact
The Electronic Journal of Combinatorics, 2003
For $i\geq 0$, the $i$-cube $Q_i$ is the graph on $2^i$ vertices representing $0/1$ tuples of len... more For $i\geq 0$, the $i$-cube $Q_i$ is the graph on $2^i$ vertices representing $0/1$ tuples of length $i$, where two vertices are adjacent whenever the tuples differ in exactly one position. (In particular, $Q_0 = K_1$.) Let $\alpha_i(G)$ be the number of induced $i$-cubes of a graph $G$. Then the cube polynomial $c(G,x)$ of $G$ is introduced as $\sum_{i\geq 0} \alpha_i(G) x^i$. It is shown that any function $f$ with two related, natural properties, is up to the factor $f(Q_0,x)$ the cube polynomial. The derivation $\partial\, G$ of a median graph $G$ is introduced and it is proved that the cube polynomial is the only function $f$ with the property $f'(G,x)= f(\partial\, G, x)$ provided that $f(G,0)=|V(G)|$. As the main application of the new concept, several relations that widely generalize previous such results for median graphs are proved. For instance, it is shown that for any $s\geq 0$ we have $c^{(s)}(G,x+1) = \sum_{i\geq s}\, {{c^{(i)}(G,x)}\over {(i-s)!}}\,,$ where certai...
Bookmarks Related papers MentionsView impact
Journal of Graph Theory, 2006
The cube polynomial c(G,x) of a graph G is defined as $\sum\nolimits_{i \ge 0} {\alpha _i ( G)x^i... more The cube polynomial c(G,x) of a graph G is defined as $\sum\nolimits_{i \ge 0} {\alpha _i ( G)x^i }$, where αi(G) denotes the number of induced i‐cubes of G, in particular, α0(G) = |V(G)| and α1(G) = |E(G)|. Let G be a median graph. It is proved that every rational zero of c(G,x) is of the form −((t + 1)/t for some integer t > 0 and that c(G,x) always has a real zero in the interval [−2,−1). Moreover, c(G,x) has a p‐multiple zero if and only if G is the Cartesian product of p trees all of the same order. Graphs of acyclic cubical complexes are characterized as the graphs G for which c(H, −2) = 0 holds for every 2‐connected convex subgraph H of G. Median graphs that are Cartesian products are also characterized. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 37–50, 2006
Bookmarks Related papers MentionsView impact
Electronic Notes in Discrete Mathematics, 2001
ABSTRACT
Bookmarks Related papers MentionsView impact
A rich structure theory has been developed in the last three decades for graphs embeddable into h... more A rich structure theory has been developed in the last three decades for graphs embeddable into hypercubes, in particular for isometric subgraphs of hypercubes, also known as partial cubes, and for median graphs. Median graphs, which constitute a proper ...
Bookmarks Related papers MentionsView impact
Discrete Mathematics, 2000
Bookmarks Related papers MentionsView impact
Bookmarks Related papers MentionsView impact
Discrete Mathematics, 1998
Bookmarks Related papers MentionsView impact
Discrete Applied Mathematics, 2011
Bookmarks Related papers MentionsView impact
Discrete Mathematics, 2000
Bookmarks Related papers MentionsView impact
Bookmarks Related papers MentionsView impact
Discrete Mathematics
Bookmarks Related papers MentionsView impact
Ars Mathematica Contemporanea, 2021
Bookmarks Related papers MentionsView impact
The Art of Discrete and Applied Mathematics, 2021
Bookmarks Related papers MentionsView impact
The Art of Discrete and Applied Mathematics, 2018
Bookmarks Related papers MentionsView impact
Applied Mathematics and Nonlinear Sciences, 2018
Balaban index is defined as J ( G ) = m m − n + 2 Σ 1 w ( u ) ⋅ w ( v ) , $J\left( G \right)=\fra... more Balaban index is defined as J ( G ) = m m − n + 2 Σ 1 w ( u ) ⋅ w ( v ) , $J\left( G \right)=\frac{m}{m-n+2}\Sigma \frac{1}{\sqrt{w\left( u \right)\cdot w\left( v \right)}},$ where the sum is taken over all edges of a connected graph G, n and m are the cardinalities of the vertex and the edge set of G, respectively, and w(u) (resp. w(v)) denotes the sum of distances from u (resp. v) to all the other vertices of G. In 2011, H. Deng found an interesting property that Balaban index is a convex function in double stars. We show that this holds surprisingly to general graphs by proving that attaching leaves at two vertices in a graph yields a new convexity property of Balaban index. We demonstrate this property by finding, for each n, seven trees with the maximum value of Balaban index, and we conclude the paper with an interesting conjecture.
Bookmarks Related papers MentionsView impact
Applied Mathematics and Computation, 2017
Bookmarks Related papers MentionsView impact
Applied Mathematics and Computation, 2017
Bookmarks Related papers MentionsView impact
Uploads
Papers by Riste Škrekovski