For distinct vertices
u
and
v
in a graph
G
, the
connectivity
between
u
and
v
, denoted
κ
G
(
u
,
v
)
, is the maximum number of internally disjoint
u
–
v
paths in
G
. The
average connectivity
of
G
, ...denoted
κ
¯
(
G
)
,
is the average of
κ
G
(
u
,
v
)
taken over all unordered pairs of distinct vertices
u
,
v
of
G
. Analogously, for a directed graph
D
, the
connectivity
from
u
to
v
, denoted
κ
D
(
u
,
v
)
, is the maximum number of internally disjoint directed
u
–
v
paths in
D
. The
average connectivity
of
D
, denoted
κ
¯
(
D
)
, is the average of
κ
D
(
u
,
v
)
taken over all ordered pairs of distinct vertices
u
,
v
of
D
. An
orientation
of a graph
G
is a directed graph obtained by assigning a direction to every edge of
G
. For a graph
G
, let
κ
¯
max
(
G
)
denote the maximum average connectivity among all orientations of
G
. In this paper we obtain bounds for
κ
¯
max
(
G
)
and for the ratio
κ
¯
max
(
G
)
/
κ
¯
(
G
)
for all graphs
G
of a given order and in a given class of graphs. Whenever possible, we demonstrate sharpness of these bounds. This problem had previously been studied for trees. We focus on the classes of cubic 3-connected graphs, minimally 2-connected graphs, 2-trees, and maximal outerplanar graphs.
Antisquares and Critical Exponents Baranwal, Aseem; Currie, James; Mol, Lucas ...
Discrete Mathematics and Theoretical Computer Science,
09/2023, Letnik:
25, Številka:
2
Journal Article
Recenzirano
Odprti dostop
The (bitwise) complement $\overline{x}$ of a binary word $x$ is obtained by
changing each $0$ in $x$ to $1$ and vice versa. An $\textit{antisquare}$ is a
nonempty word of the form $x\, \overline{x}$. ...In this paper, we study infinite
binary words that do not contain arbitrarily large antisquares. For example, we
show that the repetition threshold for the language of infinite binary words
containing exactly two distinct antisquares is $(5+\sqrt{5})/2$. We also study
repetition thresholds for related classes, where "two" in the previous sentence
is replaced by a larger number.
We say a binary word is $\textit{good}$ if the only antisquares it contains
are $01$ and $10$. We characterize the minimal antisquares, that is, those
words that are antisquares but all proper factors are good. We determine the
growth rate of the number of good words of length $n$ and determine the
repetition threshold between polynomial and exponential growth for the number
of good words.
The Threshold Dimension and Irreducible Graphs Mol, Lucas; Murphy, Matthew J.H.; Oellermann, Ortrud R.
Discussiones Mathematicae. Graph Theory,
02/2023, Letnik:
43, Številka:
1
Journal Article
Recenzirano
Odprti dostop
Let
be a graph, and let
,
, and
be vertices of
. If the distance between
and
does not equal the distance between
and
, then
is said to
and
. The
of
, denoted
), is the cardinality of a smallest set
...of vertices such that every pair of vertices of
is resolved by some vertex of
. The
of
, denoted
(
), is the minimum metric dimension among all graphs
having
as a spanning subgraph. In other words, the threshold dimension of
is the minimum metric dimension among all graphs obtained from
by adding edges. If
) =
(
), then
is said to be
We give two upper bounds for the threshold dimension of a graph, the first in terms of the diameter, and the second in terms of the chromatic number. As a consequence, we show that every planar graph of order
has threshold dimension
(log
). We show that several infinite families of graphs, known to have metric dimension 3, are in fact irreducible. Finally, we show that for any integers
and
with 1 ≤
, there is an irreducible graph of order
and metric dimension
The repetition threshold for binary rich words Currie, James D; Rampersad, Lucas Mol Narad
Discrete Mathematics and Theoretical Computer Science,
01/2020, Letnik:
22, Številka:
1
Journal Article
Recenzirano
Odprti dostop
A word of length n is rich if it contains n nonempty palindromic factors. An infinite word is rich if all of its finite factors are rich. Baranwal and Shallit produced an infinite binary rich word ...with critical exponent 2+square root of (2)/2 (approximately equal to 2.707) and conjectured that this was the least possible critical exponent for infinite binary rich words (i.e., that the repetition threshold for binary rich words is 2 + square root of (2)/2). In this article, we give a structure theorem for infinite binary rich words that avoid 14/5-powers (i.e., repetitions with exponent at least 2.8). As a consequence, we deduce that the repetition threshold for binary rich words is 2 + square root of (2)/2, as conjectured by Baranwal and Shallit. This resolves an open problem of Vesti for the binary alphabet; the problem remains open for larger alphabets. Keywords: rich word, repetition threshold, critical exponent, palindrome
For a graph
G, the mean subtree order of
G is the average order of a subtree of
G. In this note, we provide counterexamples to a recent conjecture of Chin, Gordon, MacPhee, and Vincent, that for ...every connected graph
G and every pair of distinct vertices
u and
v of
G, the addition of the edge between
u and
v increases the mean subtree order. In fact, we show that the addition of a single edge between a pair of nonadjacent vertices in a graph of order
n can decrease the mean subtree order by as much as n∕3 asymptotically. We propose the weaker conjecture that for every connected graph
G which is not complete, there exists a pair of nonadjacent vertices
u and
v, such that the addition of the edge between
u and
v increases the mean subtree order. We prove this conjecture in the special case that
G is a tree.
For a rational number r such that 1<r≤2, an undirected r-power is a word of the form xyx′, where the word x is nonempty, the word x′ is in {x,xR}, and we have |xyx′|/|xy|=r. The undirected repetition ...threshold for k letters, denoted URT(k), is the infimum of the set of all r such that undirected r-powers are avoidable on k letters. We first demonstrate that URT(3)=74. Then we show that URT(k)≥k−1k−2 for all k≥4. We conjecture that URT(k)=k−1k−2 for all k≥4, and we confirm this conjecture for k∈{4,5,…,21}. We then consider related problems in pattern avoidance; in particular, we find the undirected avoidability index of every binary pattern. This is an extended version of a paper presented at WORDS 2019, and it contains new and improved results.
Given a graph G in which each edge fails independently with probability q∈0,1, the all-terminal reliability of G is the probability that all vertices of G can communicate with one another, that is, ...the probability that the operational edges span the graph. The all-terminal reliability is a polynomial in q whose roots (all-terminal reliability roots) were conjectured to have modulus at most 1 by Brown and Colbourn. Royle and Sokal proved the conjecture false, finding roots of modulus larger than 1 by a slim margin. Here, we present the first nontrivial upper bound on the modulus of any all-terminal reliability root, in terms of the number of vertices of the graph. We also find all-terminal reliability roots of larger modulus than any previously known. Finally, we consider the all-terminal reliability roots of simple graphs; we present the smallest known simple graph with all-terminal reliability roots of modulus greater than 1, and we find simple graphs with all-terminal reliability roots of modulus greater than 1 that have higher edge connectivity than any previously known examples.
A square-free word $w$ over a fixed alphabet $\Sigma$ is extremal if every word obtained from $w$ by inserting a single letter from $\Sigma$ (at any position) contains a square. Grytczuk et al. ...recently introduced the concept of extremal square-free word and demonstrated that there are arbitrarily long extremal square-free ternary words. We find all lengths which admit an extremal square-free ternary word. In particular, we show that there is an extremal square-free ternary word of every sufficiently large length. We also solve the analogous problem for circular words.
PDF
