A bound on judicious bipartitions of directed graphs

Judicious partitioning problems on graphs ask for partitions that bound several quantities simultaneously,which have received much attention lately.Scott(2005)asked the following natural question:What is the maximum constant cdsuch that every directed graph D with m arcs and minimum outdegree d admits a bipartition V(D)=V_1∪V_2 satisfying min{e(V_1,V_2),e(V_2,V_1)}cdm?Here,for i=1,2,e(V_i,V_3-i)denotes the number of arcs in D from V_i to V_3-i.Lee et al.(2016)conjectured that every directed graph D with m arcs and minimum outdegree at least d 2 admits a bipartition V(D)=V_1∪V_2 such that min{e(V_1,V_2),e(V_2,V_1)}≥((d-1)/(2(2 d-1))+o(1))m.In this paper,we show that this conjecture holds under the additional natural condition that the minimum indegree is also at least d.     

On the number of hypercubic bipartitions of an integer

For n≤2^k$n\le 2^k$ we study the maximum number of edges of an induced subgraph on n$n$ vertices of the k$k$-dimensional hypercube _Qk$Q_k$. In the process we revisit a well-known divide-and-conquer maximin recurrence f(n)=max(min(_n1,_n2)+f(_n1)+f(_n2))$f\left(n\right)=max(min(n_1,n_2)+f\left(n_1\right)+f\left(n_2\right))$ where the maximum is taken over all proper bipartitions n=_n1+_n2$n=n_1+n_2$. We first use known results to present a characterization of those bipartitions n=_n1+_n2$n=n_1+n_2$ that yield the maximum f(n)=min(_n1,_n2)+f(_n1)+f(_n2)$f\left(n\right)=min(n_1,n_2)+f\left(n_1\right)+f\left(n_2\right)$. Then we use this characterization to present the main result of this article, namely, for a given n∈N$n\in \mathbb{N}$, the determination of the number h(n)$h\left(n\right)$ of these bipartitions that yield the said maximum f(n)$f\left(n\right)$. We present recursive formulae for h(n)$h\left(n\right)$, a generating function h(x)$h\left(x\right)$, and an explicit formula for h(n)$h\left(n\right)$ in terms of a special representation of n$n$.     

On 5-regular bipartitions with even parts distinct

The Ramanujan Journal - In 2010, Andrews, Michael D. Hirschhorn and James A. Sellers considered the function ped(n), the number of partition of an integer n with even parts distinct (the odd parts...     

A note on balanced bipartitions

A balanced bipartition of a graph G is a bipartition V₁ and V₂ of V(G) such that −1≤|V₁|−|V₂|≤1. Bollobás and Scott conjectured that if G is a graph with m edges and minimum degree at least 2 then G admits a balanced bipartition V₁,V₂ such that max{e(V₁),e(V₂)}≤m/3, where e(V_i) denotes the number of edges of G with both ends in V_i. In this note, we prove this conjecture for graphs with average degree at least 6 or with minimum degree at least 5. Moreover, we show that if G is a graph with m edges and n vertices, and if the maximum degree Δ(G)=o(n) or the minimum degree δ(G)→∞, then G admits a balanced bipartition V₁,V₂ such that max{e(V₁),e(V₂)}≤(1+o(1))m/4, answering a question of Bollobás and Scott in the affirmative. We also provide a sharp lower bound on max{e(V₁,V₂):V₁,V₂ is a balanced bipartition of G}, in terms of size of a maximum matching, where e(V₁,V₂) denotes the number of edges between V₁ and V₂.     

On $$\ell $$-regular bipartitions modulo $$\ell $$

Let \(B_\ell (n)\) denote the number of \(\ell \)-regular bipartitions of n. In this paper, we prove several infinite families of congruences satisfied by \(B_\ell (n)\) for \(\ell \in {\{5,7,13\}}\). For example, we show that for all \(\alpha >0\) and \(n\ge 0\),

$$\begin{aligned} B_5\left( 4^\alpha n+\frac{5\times 4^\alpha -2}{6}\right)\equiv & {} 0 \ (\text {mod}\ 5),\\ B_7\left( 5^{8\alpha }n+\displaystyle \frac{5^{8\alpha }-1}{2}\right)\equiv & {} 3^\alpha B_7(n)\ (\text {mod}\ 7) \end{aligned}$$

and

$$\begin{aligned} B_{13}\left( 5^{12\alpha }n+5^{12\alpha }-1\right) \equiv B_{13}(n)\ (\text {mod}\ 13). \end{aligned}$$

     

Congruences for bipartitions with odd parts distinct

Hirschhorn and Sellers studied arithmetic properties of the number of partitions with odd parts distinct. In another direction, Hammond and Lewis investigated arithmetic properties of the number of bipartitions. In this paper, we consider the number of bipartitions with odd parts distinct. Let this number be denoted by pod _?2(n). We obtain two Ramanujan-type identities for pod _?2(n), which imply that pod _?2(2n+1) is even and pod _?2(3n+2) is divisible by 3. Furthermore, we show that for any α≥1 and n≥0, \(\mathit{pod}_{-2}(3^{2\alpha+1}n+\frac{23\times 3^{2\alpha}-7}{8}) \) is a multiple of 3 and \(\mathit{pod}_{-2}(5^{\alpha+1}n+\frac{11\times5^{\alpha}+1}{4})\) is divisible by 5. We also find combinatorial interpretations for the two congruences modulo 2 and 3.     

On s-hamiltonian line graphs of claw-free graphs

For an integer $s\ge 0$, a graph $G$ is $s$-hamiltonian if for any vertex subset $S?V\left(G\right)$ with $\left|S\right|\le s$, $G?S$ is hamiltonian, and $G$ is $s$-hamiltonian connected if for any vertex subset $S?V\left(G\right)$ with $\left|S\right|\le s$, $G?S$ is hamiltonian connected. Thomassen in 1984 conjectured that every 4-connected line graph is hamiltonian (see Thomassen, 1986), and Ku?zel and Xiong in 2004 conjectured that every 4-connected line graph is hamiltonian connected (see Ryjá?ek and Vrána, 2011). In Broersma and Veldman (1987), Broersma and Veldman raised the characterization problem of $s$-hamiltonian line graphs. In Lai and Shao (2013), it is conjectured that for $s\ge 2$, a line graph $L\left(G\right)$ is $s$-hamiltonian if and only if $L\left(G\right)$ is $(s+2)$-connected. In this paper we prove the following.(i) For an integer $s\ge 2$, the line graph $L\left(G\right)$ of a claw-free graph $G$ is $s$-hamiltonian if and only if $L\left(G\right)$ is $(s+2)$-connected.(ii) The line graph $L\left(G\right)$ of a claw-free graph $G$ is 1-hamiltonian connected if and only if $L\left(G\right)$ is 4-connected.     

Arithmetic properties of bipartitions with even parts distinct

In this work, we consider various arithmetic properties of the function ped _?2(n) that denotes the number of bipartitions of n with even parts distinct. We prove two infinite families of congruences for p _?2(n) modulo 3. We also give characterizations of ped _?2(n) modulo 2 and 4. Furthermore, for a fixed positive integer k, we show that ped _?2(n) is divisible by 2 ^k for almost all n.     

On multicolour noncomplete Ramsey graphs of star graphs

Given graphs , where k≥2, the notation

     

On distance two graphs of upper bound graphs

For a poset P=(X,≤), the upper bound graph (UB-graph) of P is the graph U=(X,E_U), where uv∈E_U if and only if u≠v and there exists m∈X such that u,v≤m. For a graph G, the distance two graph DS₂(G) is the graph with vertex set V(DS₂(G))=V(G) and u,v∈V(DS₂(G)) are adjacent if and only if d_G(u,v)=2. In this paper, we deal with distance two graphs of upper bound graphs. We obtain a characterization of distance two graphs of split upper bound graphs.     

On extremal problems of graphs and generalized graphs

Anr-graph is a graph whose basic elements are its vertices and r-tuples. It is proved that to everyl andr there is anε(l, r) so that forn>n ₀ everyr-graph ofn vertices andn ^{r−ε(l, r)} r-tuples containsr. l verticesx ^(j), 1≦j≦r, 1≦i≦l, so that all ther-tuples occur in ther-graph.     

线团-收敛图

一个图的线团图就是这个图的线图的团图。对于自然数n，一个图被称为n-线团－收敛的，如果它的n次线团图同构于一个固定的图。否则称之为发散的。本刻画了线团－收敛图与发散图，给出一个线团－收敛图的构造方法，并且，讨论了线团－收敛图的线团－收敛指数。     

On hamiltonian-connected graphs

One of the most fundamental results concerning paths in graphs is due to Ore: In a graph G, if deg x + deg y ≧ |V(G)| + 1 for all pairs of nonadjacent vertices x, y ? V(G), then G is hamiltonian-connected. We generalize this result using set degrees. That is, for S ? V(G), let deg S = |_x?S N(x)|, where N(x) = {v|xv ? E(G)} is the neighborhood of x. In particular we show: In a 3-connected graph G, if deg S₁ + deg S₂ ≧ |V(G)| + 1 for each pair of distinct 2-sets of vertices S₁, S₂ ? V(G), then G is hamiltonian-connected. Several corollaries and related results are also discussed.     

On clique-critical graphs

A graph G is clique-critical if G and G?x have different clique-graphs for all vertices x of G. For any graph H, there is at most a finite number of different clique-critical graphs G such that H is the clique-graph of G. Upper and lower bounds for the number of vertices of the cliques of the critical graphs are obtained.     

On unretractive graphs

The present paper proves necessary and sufficient conditions for both lexicographic products and arbitrary graphs to be unretractive. The paper also proves that the automorphism group of a lexicographic product of graphs is isomorphic to a wreath product of a monoid with a small category.     

On unimodular graphs

We study graphs whose adjacency matrices have determinant equal to 1 or −1, and characterize certain subclasses of these graphs. Graphs whose adjacency matrices are totally unimodular are also characterized. For bipartite graphs having a unique perfect matching, we provide a formula for the inverse of the corresponding adjacency matrix, and address the problem of when that inverse is diagonally similar to a nonnegative matrix. Special attention is paid to the case that such a graph is unicyclic.