Toll number of the Cartesian and the lexicographic product of graphs

Toll convexity is a variation of the so-called interval convexity. A tolled walk $T$ between two non-adjacent vertices $u$ and $v$ in a graph $G$ is a walk, in which $u$ is adjacent only to the second vertex of $T$ and $v$ is adjacent only to the second-to-last vertex of $T$. A toll interval between $u,v\in V\left(G\right)$ is a set $T_G(u,v)=\{x\in V\left(G\right):x\text{ lies on a tolled walk between }u\text{ and }v\}$. A set $S?V\left(G\right)$ is toll convex, if $T_G(u,v)?S$ for all $u,v\in S$. A toll closure of a set $S?V\left(G\right)$ is the union of toll intervals between all pairs of vertices from $S$. The size of a smallest set $S$ whose toll closure is the whole vertex set is called a toll number of a graph $G$, $tn\left(G\right)$. The first part of the paper reinvestigates the characterization of convex sets in the Cartesian product of two graphs. It is proved that the toll number of the Cartesian product of two graphs equals 2. In the second part, the toll number of the lexicographic product of two graphs is studied. It is shown that if $H$ is not isomorphic to a complete graph, $tn(G°H)\le 3?tn\left(G\right)$. We give some necessary and sufficient conditions for $tn(G°H)=3?tn\left(G\right)$. Moreover, if $G$ has at least two extreme vertices, a complete characterization is given. Furthermore, graphs with $tn(G°H)=2$ are characterized. Finally, the formula for $tn(G°H)$ is given — it is described in terms of the so-called toll-dominating triples or, if $H$ is complete, toll-dominating pairs.     

Game chromatic number of strong product graphs

The graph coloring game is a two-player game in which the two players properly color an uncolored vertex of G alternately. The first player wins the game if all vertices of G are colored, and the second wins otherwise. The game chromatic number of a graph G is the minimum integer k such that the first player has a winning strategy for the graph coloring game on G with k colors. There is a lot of literature on the game chromatic number of graph products, e.g., the Cartesian product and the lexicographic product. In this paper, we investigate the game chromatic number of the strong product of graphs, which is one of major graph products. In particular, we completely determine the game chromatic number of the strong product of a double star and a complete graph. Moreover, we estimate the game chromatic number of some King's graphs, which are the strong products of two paths.     

Domination game and minimal edge cuts

In this paper a relationship is established between the domination game and minimal edge cuts. It is proved that the game domination number of a connected graph can be bounded above in terms of the size of minimal edge cuts. In particular, if $C$ a minimum edge cut of a connected graph $G$, then ${\gamma }_g\left(G\right)\le {\gamma }_g(G?C)+2{\kappa }^{\prime }\left(G\right)$. Double-Staller graphs are introduced in order to show that this upper bound can be attained for graphs with a bridge. The obtained results are used to extend the family of known traceable graphs whose game domination numbers are at most one-half their order. Along the way two technical lemmas, which seem to be generally applicable for the study of the domination game, are proved.     

Detecting strong cliques

A strong clique in a graph is a clique intersecting every maximal independent set. We study the computational complexity of six algorithmic decision problems related to strong cliques in graphs and almost completely determine their complexity in the classes of chordal graphs, weakly chordal graphs, line graphs and their complements, and graphs of maximum degree at most three. Our results rely on connections with matchings and relate to several graph properties studied in the literature, including well-covered graphs, localizable graphs, and general partition graphs.     

Note on 3-choosability of planar graphs with maximum degree 4

Deciding whether a planar graph (even of maximum degree 4) is 3-colorable is NP-complete. Determining subclasses of planar graphs being 3-colorable has a long history, but since Grötzsch’s result that triangle-free planar graphs are such, most of the effort was focused to solving Havel’s and Steinberg’s conjectures. In this paper, we prove that every planar graph obtained as a subgraph of the medial graph of any bipartite plane graph is 3-choosable. These graphs are allowed to have close triangles (even incident), and have no short cycles forbidden, hence representing an entirely different class than the graphs inferred by the above mentioned conjectures.     

DP-3-coloring of some planar graphs

In this article, we use a unified approach to prove several classes of planar graphs are DP-3-colorable, which extend the corresponding results on 3-choosability.     

On induced and isometric embeddings of graphs into the strong product of paths

The strong isometric dimension and the adjacent isometric dimension of graphs are compared. The concepts are equivalent for graphs of diameter 2 in which case the problem of determining these dimensions can be reduced to a covering problem with complete bipartite graphs. Using this approach several exact strong and adjacent dimensions are computed (for instance of the Petersen graph) and a positive answer is given to the Problem 4.1 of Fitzpatrick and Nowakowski [The strong isometric dimension of finite reflexive graphs, Discuss. Math. Graph Theory 20 (2000) 23-38] whether there is a graph G with the strong isometric dimension bigger that ⌈|V(G)|/2⌉.     

Nowhere-zero 3-flow of graphs with small independence number

Tutte’s $3$-flow conjecture states that every $4$-edge-connected graph admits a nowhere-zero $3$-flow. In this paper, we characterize all graphs with independence number at most $4$ that admit a nowhere-zero $3$-flow. The characterization of $3$-flow verifies Tutte’s $3$-flow conjecture for graphs with independence number at most $4$ and with order at least $21$. In addition, we prove that every odd-$5$-edge-connected graph with independence number at most $3$ admits a nowhere-zero $3$-flow. To obtain these results, we introduce a new reduction method to handle odd wheels.     

Bandwidth of the strong product of two connected graphs

The bandwidth B(G) of a graph G is the minimum of the quantity max{|f(x)-f(y)|:xy∈E(G)} taken over all proper numberings f of G. The strong product of two graphs G and H, written as G(S_P)H, is the graph with vertex set V(G)×V(H) and with (u₁,v₁) adjacent to (u₂,v₂) if one of the following holds: (a) u₁ and v₁ are adjacent to u₂ and v₂ in G and H, respectively, (b) u₁ is adjacent to u₂ in G and v₁=v₂, or (c) u₁=u₂ and v₁ is adjacent to v₂ in H. In this paper, we investigate the bandwidth of the strong product of two connected graphs. Let G be a connected graph. We denote the diameter of G by D(G). Let d be a positive integer and let x,y be two vertices of G. Let denote the set of vertices v so that the distance between x and v in G is at most d. We define δ_d(G) as the minimum value of over all vertices x of G. Let denote the set of vertices z such that the distance between x and z in G is at most d-1 and z is adjacent to y. We denote the larger of and by . We define η(G)=1 if G is complete and η(G) as the minimum of over all pair of vertices x,y of G otherwise. Let G and H be two connected graphs. Among other results, we prove that if δ_D(H)(G)?B(G)D(H)+1 and B(H)=⌈(|V(H)|+η(H)-2)/D(H)⌉, then B(G(S_P)H)=B(G)|V(H)|+B(H). Moreover, we show that this result determines the bandwidth of the strong product of some classes of graphs. Furthermore, we study the bandwidth of the strong product of power of paths with complete bipartite graphs.     

H-free subgraphs of dense graphs maximizing the number of cliques and their blow-ups

We consider the structure of $H$-free subgraphs of graphs with high minimal degree. We prove that for every $k>m$ there exists an $???(k,m)>0$ so that the following holds. For every graph $H$ with chromatic number $k$ from which one can delete an edge and reduce the chromatic number, and for every graph $G$ on $n>n_0\left(H\right)$ vertices in which all degrees are at least $(1??)n$, any subgraph of $G$ which is $H$-free and contains the maximum number of copies of the complete graph $K_m$ is $(k?1)$-colorable.We also consider several extensions for the case of a general forbidden graph $H$ of a given chromatic number, and for subgraphs maximizing the number of copies of balanced blowups of complete graphs.     

The geodetic number of the lexicographic product of graphs

A set S of vertices of a graph G is a geodetic set if every vertex of G lies in an interval between two vertices from S. The size of a minimum geodetic set in G is the geodetic number g(G) of G. We find that the geodetic number of the lexicographic product G°H for a non-complete graph H lies between 2 and 3g(G). We characterize the graphs G and H for which g(G°H)=2, as well as the lexicographic products T°H that enjoy g(T°H)=3g(G), when T is isomorphic to a tree. Using a new concept of the so-called geodominating triple of a graph G, a formula that expresses the exact geodetic number of G°H is established, where G is an arbitrary graph and H a non-complete graph.     

Fractional chromatic numbers of tensor products of three graphs

The tensor product $(G_1,G_2,G_3)$ of graphs $G_1$, $G_2$ and $G_3$ is defined by $V(G_1,G_2,G_3)=V\left(G_1\right)\times V\left(G_2\right)\times V\left(G_3\right)$and $E(G_1,G_2,G_3)=\left\{\left((u_1,u_2,u_3),(v_1,v_2,v_3)\right):\left|\{i:(u_i,v_i)\in E\left(G_i\right)\}\right|\ge 2\right\}.$Let ${\chi }_f\left(G\right)$ be the fractional chromatic number of a graph $G$. In this paper, we prove that if one of the three graphs $G_1$, $G_2$ and $G_3$ is a circular clique, ${\chi }_f(G_1,G_2,G_3)=min\{{\chi }_f\left(G_1\right){\chi }_f\left(G_2\right),{\chi }_f\left(G_1\right){\chi }_f\left(G_3\right),{\chi }_f\left(G_2\right){\chi }_f\left(G_3\right)\}.$     

Weight enumerators of reducible cyclic codes and their dual codes

Let ${\mathbb{F}}_q$ be a finite field and $n$ a positive integer. In this paper, we find a new combinatorial method to determine weight enumerators of reducible cyclic codes and their dual codes of length $n$ over ${\mathbb{F}}_q$, which just generalize results of Zhu et al. (2015); especially, we also give the weight enumerator of a cyclic code, which is viewed as a partial Melas code. Furthermore, weight enumerators obtained in this paper are all in the form of power of a polynomial.     

New families of graphs determined by their generalized spectrum

We construct infinite families of graphs that are determined by their generalized spectrum. This construction is based on new formulae for the determinant of the walk matrix of a graph. All graphs constructed here satisfy a certain extremal divisibility condition for the determinant of their walk matrix.     

On three color Ramsey numbers R(C4,C4,K1,n)

For $k$ given graphs $G_1,G_2,\dots ,G_k$, $k\ge 2$, the $k$-color Ramsey number, denoted by $R(G_1,G_2,\dots ,G_k)$, is the smallest integer $N$ such that if we arbitrarily color the edges of a complete graph of order $N$ with $k$ colors, then it always contains a monochromatic copy of $G_i$ colored with $i$, for some $1\le i\le k$. Let $C_m$ be a cycle of length $m$ and $K_{1,n}$ a star of order $n+1$. In this paper, firstly we give a general upper bound of $R(C_4,C_4,\dots ,C_4,K_{1,n})$. In particular, for the 3-color case, we have $R(C_4,C_4,K_{1,n})\le n+?\sqrt{4n+5}?+3$ and this bound is tight in some sense. Furthermore, we prove that $R(C_4,C_4,K_{1,n})\le n+?\sqrt{4n+5}?+2$ for all $n={?}^2??$ and $?\ge 2$, and if $?$ is a prime power, then the equality holds.     

Lower bounds for the domination number and the total domination number of direct product graphs

A sharp lower bound for the domination number and the total domination number of the direct product of finitely many complete graphs is given: . Sharpness is established in the case when the factors are large enough in comparison to the number of factors. The main result gives a lower bound for the domination (and the total domination) number of the direct product of two arbitrary graphs: γ(G×H)≥γ(G)+γ(H)−1. Infinite families of graphs that attain the bound are presented. For these graphs it also holds that γ_t(G×H)=γ(G)+γ(H)−1. Some additional parallels with the total domination number are made.     

Robust mean–variance hedging via G-expectation

In this paper we study mean–variance hedging under the $G$-expectation framework. Our analysis is carried out by exploiting the $G$-martingale representation theorem and the related probabilistic tools, in a continuous financial market with two assets, where the discounted risky one is modeled as a symmetric $G$-martingale. By tackling progressively larger classes of contingent claims, we are able to explicitly compute the optimal strategy under general assumptions on the form of the contingent claim.     

Existence of local strong solutions to fluid–beam and fluid–rod interaction systems

We study an unsteady nonlinear fluid–structure interaction problem. We consider a Newtonian incompressible two-dimensional flow described by the Navier–Stokes equations set in an unknown domain depending on the displacement of a structure, which itself satisfies a linear wave equation or a linear beam equation. The fluid and the structure systems are coupled via interface conditions prescribing the continuity of the velocities at the fluid–structure interface and the action-reaction principle. Considering three different structure models, we prove existence of a unique local-in-time strong solution, for which there is no gap between the regularity of the initial data and the regularity of the solution enabling to obtain a blow up alternative. In the case of a damped beam this is an alternative proof (and a generalization to non zero initial displacement) of the result that can be found in [20]. In the case of the wave equation or a beam equation with inertia of rotation, this is, to our knowledge the first result of existence of strong solutions for which no viscosity is added. The key points consist in studying the coupled system without decoupling the fluid from the structure and to use the fluid dissipation to control, in appropriate function spaces, the structure velocity.     

Strengthening the Murty–Simon conjecture on diameter 2 critical graphs

A graph is diameter-2-critical if its diameter is 2 but the removal of any edge increases the diameter. A well-studied conjecture, known as the Murty–Simon conjecture, states that any diameter-2-critical graph of order $n$ has at most $?n^2∕4?$ edges, with equality if and only if $G$ is a balanced complete bipartite graph. Many partial results about this conjecture have been obtained, in particular it is known to hold for all sufficiently large graphs, for all triangle-free graphs, and for all graphs with a dominating edge. In this paper, we discuss ways in which this conjecture can be strengthened. Extending previous conjectures in this direction, we conjecture that, when we exclude the class of complete bipartite graphs and one particular graph, the maximum number of edges of a diameter-2-critical graph is at most $?{(n?1)}^2∕4?+1$. The family of extremal examples is conjectured to consist of certain twin-expansions of the 5-cycle (with the exception of a set of thirteen special small graphs). Our main result is a step towards our conjecture: we show that the Murty–Simon bound is not tight for non-bipartite diameter-2-critical graphs that have a dominating edge, as they have at most $?n^2∕4??2$ edges. Along the way, we give a shorter proof of the Murty–Simon conjecture for this class of graphs, and stronger bounds for more specific cases. We also characterize diameter-2-critical graphs of order $n$ with maximum degree $n?2$: they form an interesting family of graphs with a dominating edge and $2n?4$ edges.