Minimally 3-restricted edge connected graphs

For a connected graph G=(V,E), an edge set S⊂E is a 3-restricted edge cut if G−S is disconnected and every component of G−S has order at least three. The cardinality of a minimum 3-restricted edge cut of G is the 3-restricted edge connectivity of G, denoted by λ₃(G). A graph G is called minimally 3-restricted edge connected if λ₃(G−e)<λ₃(G) for each edge e∈E. A graph G is λ₃-optimal if λ₃(G)=ξ₃(G), where , ω(U) is the number of edges between U and V?U, and G[U] is the subgraph of G induced by vertex set U. We show in this paper that a minimally 3-restricted edge connected graph is always λ₃-optimal except the 3-cube.     

Super Connectivity and Super Edge Connectivity of the Mycielskian of a Graph

Mycielski introduced a new graph transformation μ(G) for graph G, which is called the Mycielskian of G. A graph G is super connected or simply super-κ (resp. super edge connected or super-λ), if every minimum vertex cut (resp. minimum edge cut) isolates a vertex of G. In this paper, we show that for a connected graph G with |V(G)| ≥ 2, μ(G) is super-κ if and only if δ(G) < 2κ(G), and μ(G) is super-λ if and only if G\ncong K₂{G\ncong K_2}.     

Degree Bounded Spanning Trees

In this paper, we give a sufficient condition for a graph to have a degree bounded spanning tree. Let n ≥ 1, k ≥ 3, c ≥ 0 and G be an n-connected graph. Suppose that for every independent set ${S \subseteq V(G)}In this paper, we give a sufficient condition for a graph to have a degree bounded spanning tree. Let n ≥ 1, k ≥ 3, c ≥ 0 and G be an n-connected graph. Suppose that for every independent set S í V(G){S \subseteq V(G)} of cardinality n(k−1) + c + 2, there exists a vertex set X í S{X \subseteq S} of cardinality k such that the degree sum of vertices in X is at least |V(G)| − c −1. Then G has a spanning tree T with maximum degree at most k+éc/nù{k+\lceil c/n\rceil} and ?_{v ? V(T)}max{d_T(v)-k,0} ￡ c{\sum_{v\in V(T)}\max\{d_T(v)-k,0\}\leq c} .     

An Upper Bound for the Total Domination Subdivision Number of a Graph

A set S of vertices of a graph G = (V, E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γ _t (G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number sd_gt(G){{\rm sd}_{\gamma_t}(G)} is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. In this paper, we prove that sd_gt(G) ￡ 2g_t(G)-1{{\rm sd}_{\gamma_t}(G)\leq 2\gamma_t(G)-1} for every simple connected graph G of order n ≥ 3.     

Bound on <Emphasis Type="Italic">m</Emphasis>-restricted Edge Connectivity

An m-restricted edge cut is an edge cut that separates a connected graph into a disconnected one with no components having order less than m. m-restrict edge connectivity λm is the cardinality of a minimum m-restricted edge cut. Let G be a connected k-regular graph of order at least 2m that contains m-restricted edge cuts and X be a subgraph of G. Let θ(X) denote the number of edges with one end in X and the other not in X and ξm=min{θ(X) ;X is a connected vertex-induced subgraph of order m}.It is proved in this paper that if G has girth at least m/2 2,then λm≤ξm.The upper bound of λm is sharp.     

Boxicity of Circular Arc Graphs

A k-dimensional box is a Cartesian product R ₁ × · · · × R _k where each R _i is a closed interval on the real line. The boxicity of a graph G, denoted as box(G), is the minimum integer k such that G can be represented as the intersection graph of a collection of k-dimensional boxes. That is, two vertices are adjacent if and only if their corresponding boxes intersect. A circular arc graph is a graph that can be represented as the intersection graph of arcs on a circle. We show that if G is a circular arc graph which admits a circular arc representation in which no arc has length at least p(\fraca-1a){\pi(\frac{\alpha-1}{\alpha})} for some a ? \mathbbN _{3 2}{\alpha\in\mathbb{N}_{\geq 2}}, then box(G) ≤ α (Here the arcs are considered with respect to a unit circle). From this result we show that if G has maximum degree D < ?\fracn(a-1)2a?{\Delta < \lfloor{\frac{n(\alpha-1)}{2\alpha}}\rfloor} for some a ? \mathbbN _{3 2}{\alpha \in \mathbb{N}_{\geq 2}}, then box(G) ≤ α. We also demonstrate a graph having box(G) > α but with D = n\frac(a-1)2a+ \fracn2a(a+1)+(a+2){\Delta=n\frac{(\alpha-1)}{2\alpha}+ \frac{n}{2\alpha(\alpha+1)}+(\alpha+2)}. For a proper circular arc graph G, we show that if D < ?\fracn(a-1)a?{\Delta < \lfloor{\frac{n(\alpha-1)}{\alpha}}\rfloor} for some a ? \mathbbN _{3 2}{\alpha\in \mathbb{N}_{\geq 2}}, then box(G) ≤ α. Let r be the cardinality of the minimum overlap set, i.e. the minimum number of arcs passing through any point on the circle, with respect to some circular arc representation of G. We show that for any circular arc graph G, box(G) ≤ r + 1 and this bound is tight. We show that if G admits a circular arc representation in which no family of k ≤ 3 arcs covers the circle, then box(G) ≤ 3 and if G admits a circular arc representation in which no family of k ≤ 4 arcs covers the circle, then box(G) ≤ 2. We also show that both these bounds are tight.     

Extra edge connectivity and isoperimetric edge connectivity

An edge set S of a connected graph G is a k-extra edge cut, if G-S is no longer connected, and each component of G-S has at least k vertices. The cardinality of a minimum k-extra edge cut, denoted by λ_k(G), is the k-extra edge connectivity of G. The kth isoperimetric edge connectivity γ_k(G) is defined as , where ω(U) is the number of edges with one end in U and the other end in . Write β_k(G)=min{ω(U):U⊂V(G),|U|=k}. A graph G with is said to be γ_k-optimal.In this paper, we first prove that λ_k(G)=γ_k(G) if G is a regular graph with girth g?k/2. Then, we show that except for K_3,3 and K₄, a 3-regular vertex/edge transitive graph is γ_k-optimal if and only if its girth is at least k+2. Finally, we prove that a connected d-regular edge-transitive graph with d?6e_k(G)/k is γ_k-optimal, where e_k(G) is the maximum number of edges in a subgraph of G with order k.     

On the Perfect Matchings of Near Regular Graphs

Let k, h be positive integers with k ≤ h. A graph G is called a [k, h]-graph if k ≤ d(v) ≤ h for any v ? V(G){v \in V(G)}. Let G be a [k, h]-graph of order 2n such that k ≥ n. Hilton (J. Graph Theory 9:193–196, 1985) proved that G contains at least ?k/3?{\lfloor k/3\rfloor} disjoint perfect matchings if h = k. Hilton’s result had been improved by Zhang and Zhu (J. Combin. Theory, Series B, 56:74–89, 1992), they proved that G contains at least ?k/2?{\lfloor k/2\rfloor} disjoint perfect matchings if k = h. In this paper, we improve Hilton’s result from another direction, we prove that Hilton’s result is true for [k, k + 1]-graphs. Specifically, we prove that G contains at least ?\fracn3?+1+(k-n){\lfloor\frac{n}3\rfloor+1+(k-n)} disjoint perfect matchings if h = k + 1.     

Characterization of $ {\mathbb{A}_{16}} $ by a noncommuting graph

Let G be a finite non-Abelian group. We define a graph Γ _G ; called the noncommuting graph of G; with a vertex set G − Z(G) such that two vertices x and y are adjacent if and only if xy ≠ yx: Abdollahi, Akbari, and Maimani put forward the following conjecture (the AAM conjecture): If S is a finite non-Abelian simple group and G is a group such that Γ _S ≅ Γ _G ; then S ≅ G: It is still unknown if this conjecture holds for all simple finite groups with connected prime graph except \mathbbA₁₀ {\mathbb{A}_{10}} , L ₄(8), L ₄(4), and U ₄(4). In this paper, we prove that if \mathbbA₁₆ {\mathbb{A}_{16}} denotes the alternating group of degree 16; then, for any finite group G; the graph isomorphism G_\mathbbA16 @ G_G {\Gamma_{{\mathbb{A}_{16}}}} \cong {\Gamma_G} implies that \mathbbA₁₆ @ G {\mathbb{A}_{16}} \cong G .     

Vertex-Distinguishing Edge Colorings of Graphs with Degree Sum Conditions

An edge coloring is called vertex-distinguishing if every two distinct vertices are incident to different sets of colored edges. The minimum number of colors required for a vertex-distinguishing proper edge coloring of a simple graph G is denoted by c￠_vd(G){\chi'_{vd}(G)}. It is proved that c￠_vd(G) ￡ D(G)+5{\chi'_{vd}(G)\leq\Delta(G)+5} if G is a connected graph of order n ≥ 3 and s₂(G) 3 \frac2n3{\sigma_{2}(G)\geq\frac{2n}{3}}, where σ ₂(G) denotes the minimum degree sum of two nonadjacent vertices in G.     

Super Restricted Edge Connectivity of Regular Graphs

An edge cut of a connected graph is called restricted if it separates this graph into components each having order at least 2; a graph G is super restricted edge connected if G−S contains an isolated edge for every minimum restricted edge cut S of G. It is proved in this paper that k-regular connected graph G is super restricted edge connected if k > |V(G)|/2+1. The lower bound on k is exemplified to be sharp to some extent. With this observation, we determined the number of edge cuts of size at most 2k−2 of these graphs. Supported by NNSF of China (10271105); Ministry of Science and Technology of Fujian (2003J036); Education Ministry of Fujian (JA03147)     

On Linear Fractional Transformations Associated with Generalized J-Inner Matrix Functions

A class U_k1 (J){\mathcal{U}}_{\kappa 1} (J) of generalized J-inner mvf’s (matrix valued functions) W(λ) which appear as resolvent matrices for bitangential interpolation problems in the generalized Schur class of p ×q  mvf￠s S_k^{p ×q}p \times q \, {\rm mvf's}\, {\mathcal{S}}_{\kappa}^{p \times q} and some associated reproducing kernel Pontryagin spaces are studied. These spaces are used to describe the range of the linear fractional transformation T_W based on W and applied to S_k2^{p ×q}{\mathcal{S}}_{\kappa 2}^{p \times q}. Factorization formulas for mvf’s W in a subclass U^°_k1 (J) of U_k1(J){\mathcal{U}^{\circ}_{\kappa 1}} (J)\, {\rm of}\, {\mathcal{U}}_{\kappa 1}(J) found and then used to parametrize the set S_k1+k2^{p ×q} ?T_W [ S_k2^{p ×q} ]{\mathcal{S}}_{{\kappa 1}+{\kappa 2}}^{p \times q} \cap T_{W} \left[ {\mathcal{S}}_{\kappa 2}^{p \times q} \right]. Applications to bitangential interpolation problems in the class S_k1+k2^{p ×q}{\mathcal{S}}_{{\kappa 1}+{\kappa 2}}^{p \times q} will be presented elsewhere.     

On Super Restricted Edge Connectivity of Half Vertex Transitive Graphs

Let X =  (V, E) be a connected graph. Call X super restricted edge connected in short, sup-λ′, if F is a minimum edge set of X such that X − F is disconnected and every component of X − F has at least two vertices, then F is the set of edges adjacent to a certain edge with minimum edge degree in X. A bipartite graph is said to be half vertex transitive if its automorphism group is transitive on the sets of its bipartition. In this article, we show that every connected half vertex transitive graph X with n =  |V(X)| ≥  4 and X \ncong K_1,n-1{X \ncong K_{1,n-1}} is λ′-optimal. By studying the λ′-superatoms of X, we characterize sup-λ′ connected half vertex transitive graphs. As a corollary, sup-λ′ connected Bi-Cayley graphs are also characterized.     

A k-Tree Containing Specified Vertices

A k-tree is a tree with maximum degree at most k. In this paper, we give sufficient conditions for a graph to have a k-tree containing specified vertices. Let k be an integer with k > 3. Let G be a graph of order n and let ${S \subseteq V(G)}A k-tree is a tree with maximum degree at most k. In this paper, we give sufficient conditions for a graph to have a k-tree containing specified vertices. Let k be an integer with k > 3. Let G be a graph of order n and let S í V(G){S \subseteq V(G)} with κ(S) ≥ 1. Suppose that for every l > κ(S), there exists an integer t such that 1 ￡ t ￡ (k-1)l+2 - ?\fracl-1k ?{1 \le t \leq (k-1)l+2 - \lfloor \frac{l-1}{k} \rfloor} and the degree sum of any t independent vertices of S is at least n + tl − kl − 1. Then G has a k-tree containing S. We also show some new results on a spanning k-tree as corollaries of the above theorem.     

An Introduction to Closed/Open Neighborhood Sums: Minimax, Maximin, and Spread

For a graph G of order |V(G)| = n and a real-valued mapping f:V(G)?\mathbbR{f:V(G)\rightarrow\mathbb{R}}, if S ì V(G){S\subset V(G)} then f(S)=?_{w ? S} f(w){f(S)=\sum_{w\in S} f(w)} is called the weight of S under f. The closed (respectively, open) neighborhood sum of f is the maximum weight of a closed (respectively, open) neighborhood under f, that is, NS[f]=max{f(N[v])|v ? V(G)}{NS[f]={\rm max}\{f(N[v])|v \in V(G)\}} and NS(f)=max{f(N(v))|v ? V(G)}{NS(f)={\rm max}\{f(N(v))|v \in V(G)\}}. The closed (respectively, open) lower neighborhood sum of f is the minimum weight of a closed (respectively, open) neighborhood under f, that is, NS^-[f]=min{f(N[v])|v ? V(G)}{NS^{-}[f]={\rm min}\{f(N[v])|v\in V(G)\}} and NS^-(f)=min{f(N(v))|v ? V(G)}{NS^{-}(f)={\rm min}\{f(N(v))|v\in V(G)\}}. For W ì \mathbbR{W\subset \mathbb{R}}, the closed and open neighborhood sum parameters are NS_W[G]=min{NS[f]|f:V(G)? W{NS_W[G]={\rm min}\{NS[f]|f:V(G)\rightarrow W} is a bijection} and NS_W(G)=min{NS(f)|f:V(G)? W{NS_W(G)={\rm min}\{NS(f)|f:V(G)\rightarrow W} is a bijection}. The lower neighbor sum parameters are NS^-_W[G]=maxNS^-[f]|f:V(G)? W{NS^{-}_W[G]={\rm max}NS^{-}[f]|f:V(G)\rightarrow W} is a bijection} and NS^-_W(G)=maxNS^-(f)|f:V(G)? W{NS^{-}_W(G)={\rm max}NS^{-}(f)|f:V(G)\rightarrow W} is a bijection}. For bijections f:V(G)? {1,2,?,n}{f:V(G)\rightarrow \{1,2,\ldots,n\}} we consider the parameters NS[G], NS(G), NS ⁻[G] and NS ⁻(G), as well as two parameters minimizing the maximum difference in neighborhood sums.     

On approximation of periodic functions by Fourier sums

Let L _p , 1 ≤ p< ∞, be the space of 2π-periodic functions f with the norm || f ||_p = ( ò _{- p}^p | f |^p )^{1 \mathord}

Total Domination in Partitioned Graphs

We present results on total domination in a partitioned graph G = (V, E). Let γ _t (G) denote the total dominating number of G. For a partition , k ≥ 2, of V, let γ _t (G; V _i ) be the cardinality of a smallest subset of V such that every vertex of V _i has a neighbour in it and define the following