Fractional f-Edge Cover Chromatic Index of Graphs

Let G be a graph, and let f be an integer function on V with ${1\leq f(v)\leq d(v)}$ to each vertex ${\upsilon \in V}$ . An f-edge cover coloring is a coloring of edges of E(G) such that each color appears at each vertex ${\upsilon \in V(G)}$ at least f(υ) times. The maximum number of colors needed to f-edge cover color G is called the f-edge cover chromatic index of G and denoted by ${\chi^{'}_{fc}(G)}$ . It is well known that any simple graph G has the f-edge cover chromatic index equal to δ _f (G) or δ _f (G) ? 1, where ${\delta_{f}(G)=\,min\{\lfloor \frac{d(v)}{f(v)} \rfloor: v\in V(G)\}}$ . The fractional f-edge cover chromatic index of a graph G, denoted by ${\chi^{'}_{fcf}(G)}$ , is the fractional f-matching number of the edge f-edge cover hypergraph ${\mathcal{H}}$ of G whose vertices are the edges of G and whose hyperedges are the f-edge covers of G. In this paper, we give an exact formula of ${\chi^{'}_{fcf}(G)}$ for any graph G, that is, ${\chi^{'}_{fcf}(G)=\,min \{\min\limits_{v\in V(G)}d_{f}(v), \lambda_{f}(G)\}}$ , where ${\lambda_{f}(G)=\min\limits_{S} \frac{|C[S]|}{\lceil (\sum\limits_{v\in S}{f(v)})/2 \rceil}}$ and the minimum is taken over all nonempty subsets S of V(G) and C[S] is the set of edges that have at least one end in S.     

On All Fractional （a,b, k）-Critical Graphs

Let a,b,k,r be nonnegative integers with 1≤a≤b and r≥2.LetG be a graph of order n with n(a+b)(r(a+b)-2)+ak/a.In this paper,we first show a characterization for all fractional(a,b,k)-critical graphs.Then using the result,we prove that G is all fractional(a,b,k)-critical if δ(G)≥(r-1)b2/a+k and |NG(x1)∪NG(x2)∪···∪NG(xr)|≥bn+ak/a+b for any independent subset {x1,x2,...,xr} in G.Furthermore,it is shown that the lower bound on the condition|NG(x1)∪NG(x2)∪···∪NG(xr)|≥bn+ak/a+b is best possible in some sense,and it is an extension of Lu's previous result.     

Roman domination subdivision number of graphs

A Roman dominating function on a graph G = (V, E) is a function f : V ? {0, 1, 2}f : V \rightarrow \{0, 1, 2\} satisfying the condition that every vertex v for which f(v) = 0 is adjacent to at least one vertex u for which f(u) = 2. The weight of a Roman dominating function is the value w(f) = ?_{v ? V} f(v)w(f) = \sum_{v\in V} f(v). The Roman domination number of a graph G, denoted by _gR(G)_{\gamma R}(G), equals the minimum weight of a Roman dominating function on G. The Roman domination subdivision number sd_gR(G)sd_{\gamma R}(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 Roman domination number. In this paper, first we establish upper bounds on the Roman domination subdivision number for arbitrary graphs in terms of vertex degree. Then we present several different conditions on G which are sufficient to imply that $1 \leq sd_{\gamma R}(G) \leq 3$1 \leq sd_{\gamma R}(G) \leq 3. Finally, we show that the Roman domination subdivision number of a graph can be arbitrarily large.     

Subset-Sum Representations of Domination Polynomials

The domination polynomial D(G, x) is the ordinary generating function for the dominating sets of an undirected graph G = (V, E) with respect to their cardinality. We consider in this paper representations of D(G, x) as a sum over subsets of the edge and vertex set of G. One of our main results is a representation of D(G, x) as a sum ranging over spanning bipartite subgraphs of G. Let d(G) be the number of dominating sets of G. We call a graph G conformal if all of its components are of even order. Let Con(G) be the set of all vertex-induced conformal subgraphs of G and let k(G) be the number of components of G. We show that $$d(G) = \sum \limits_{H\in{\rm Con}(G)}2^{k(H)}$$ .     

On conjugacy of some systems of functions

Summary. We investigate the bounded solutions j:[0,1]? X \varphi:[0,1]\to X of the system of functional equations¶¶j(f_k(x))=F_k(j(x)),    k=0,?,n-1,x ? [0,1] \varphi(f_k(x))=F_k(\varphi(x)),\;\;k=0,\ldots,n-1,x\in[0,1] ,(*)¶where X is a complete metric space, f₀,?,f_n-1:[0,1]?[0,1] f_0,\ldots,f_{n-1}:[0,1]\to[0,1] and F₀,...,F_n-1:X? X F_0,...,F_{n-1}:X\to X are continuous functions fulfilling the boundary conditions f₀(0) = 0, f_n-1(1) = 1, f_k+1(0) = f_k(1), F₀(a) = a,F_n-1(b) = b,F_k+1(a) = F_k(b), k = 0,?,n-2 f_{0}(0) = 0, f_{n-1}(1) = 1, f_{k+1}(0) = f_{k}(1), F_{0}(a) = a,F_{n-1}(b) = b,F_{k+1}(a) = F_{k}(b),\,k = 0,\ldots,n-2 , for some a,b ? X a,b\in X . We give assumptions on the functions f_k and F_k which imply the existence, uniqueness and continuity of bounded solutions of the system (*). In the case X = \Bbb C X= \Bbb C we consider some particular systems (*) of which the solutions determine some peculiar curves generating some fractals. If X is a closed interval we give a collection of conditions which imply respectively the existence of homeomorphic solutions, singular solutions and a.e. nondifferentiable solutions of (*).     

Critically indecomposable graphs

An undirected graph G=(V,E) with a specific subset X⊂V is called X-critical if G and G(X), induced subgraph on X, are indecomposable but G(V−{w}) is decomposable for every w∈V−X. This is a generalization of critically indecomposable graphs studied by Schmerl and Trotter [J.H. Schmerl, W.T. Trotter, Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Mathematics 113 (1993) 191-205] and Bonizzoni [P. Bonizzoni, Primitive 2-structures with the (n−2)-property, Theoretical Computer Science 132 (1994) 151-178], who deal with the case where X is empty.We present several structural results for this class of graphs and show that in every X-critical graph the vertices of V−X can be partitioned into pairs (a₁,b₁),(a₂,b₂),…,(a_m,b_m) such that G(V−{a_j1,b_j1,…,a_jk,b_jk}) is also an X-critical graph for arbitrary set of indices {j₁,…,j_k}. These vertex pairs are called commutative elimination sequence. If G is an arbitrary indecomposable graph with an indecomposable induced subgraph G(X), then the above result establishes the existence of an indecomposability preserving sequence of vertex pairs (x₁,y₁),…,(x_t,y_t) such that x_i,y_i∈V−X. As an application of the commutative elimination sequence of an X-critical graph we present algorithms to extend a 3-coloring (similarly, 1-factor) of G(X) to entire G.     

A Neighborhood Union Condition for Fractional ID-[<Emphasis Type="Italic">a</Emphasis>, <Emphasis Type="Italic">b</Emphasis>]-factor-critical Graphs

Let a, b, r be nonnegative integers with \(1\leq{a}\leq{b}\) and \(r\geq2\). Let G be a graph of order n with \(n >\frac{(a+2b)(r(a+b)-2)}{b}\). In this paper, we prove that G is fractional ID-[a, b]-factor-critical if \(\delta(G)\geq\frac{bn}{a+2b}+a(r-1)\) and \(\mid N_{G}(x_{1}) \cup N_{G}(x_{2}) \cup \cdotp \cdotp \cdotp \cup N_{G}(x_{r})\mid\geq\frac{(a+b)n}{a+2b}\) for any independent subset {x₁, x₂, · · ·, x_r} in G. It is a generalization of Zhou et al.’s previous result [Discussiones Mathematicae Graph Theory, 36: 409–418 (2016)] in which r = 2 is discussed. Furthermore, we show that this result is best possible in some sense.     

Disjoint Paths in Graphs II,A Special Case

Let G be a graph,{a,b,c} í V(G) \{a,b,c\}\subseteq V(G) , and {a￠,b￠,c￠} í V(G) \{a',b',c'\}\subseteq V(G) such that {a,b,c} 1 {a￠,b￠,c￠} \{a,b,c\}\neq \{a',b',c'\} . We say that (G,{a,c}, {a￠,c￠}, (b, b￠)) (G,\{a,c\}, \{a',c'\}, (b, b')) is an obstruction if, for any three vertex disjoint paths from {a, b, c} to {a', b', c'} in G, one path is from b to b'. In this paper, we characterize a special class of obstructions. This will be used to characterize all obstructions.     

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.     

Acyclic edge coloring of graphs with large girths

A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic chromatic index of G, denoted by χ’a(G), is the least number of colors such that G has an acyclic edge k-coloring. Let G be a graph with maximum degree Δ and girth g(G), and let 1≤r≤2Δ be an integer. In this paper, it is shown that there exists a constant c > 0 such that if g(G)≥cΔ r log(Δ2/r) then χa(G)≤Δ + r + 1, which generalizes the result of Alon et al. in 2001. When G is restricted to series-parallel graphs, it is proved that χ’a(G) = Δ if Δ≥4 and g(G)≥4; or Δ≥3 and g(G)≥5.     

The Cycle Discrepancy of Three-Regular Graphs

Let G = (V, E) be an undirected graph and C(G){{\mathcal C}(G)} denote the set of all cycles in G. We introduce a graph invariant cycle discrepancy, which we define as

Neighborhood Conditions for Fractional ID-<Emphasis Type="Italic">k</Emphasis>-factor-critical Graphs

Let G be a graph and k ≥ 2 a positive integer. Let h: E(G) → [0, 1] be a function. If \(\sum\limits_{e \mathrel\backepsilon x} {h(e) = k} \) holds for each x ∈ V (G), then we call G[F_h] a fractional k-factor of G with indicator function h where F_h = {e ∈ E(G): h(e) > 0}. A graph G is fractional independent-set-deletable k-factor-critical (in short, fractional ID-k-factor-critical), if G ? I has a fractional k-factor for every independent set I of G. In this paper, we prove that if n ≥ 9k ? 14 and for any subset X ? V (G) we have

$${N_G}(X) = V(G)if|X| \geqslant \left\lfloor {\frac{{kn}}{{3k - 1}}} \right\rfloor ;or|{N_G}(X)| \geqslant \frac{{3k - 1}}{k}|X|if|X| < \left\lfloor {\frac{{kn}}{{3k - 1}}} \right\rfloor ,$$

then G is fractional ID-k-factor-critical.

     

Decomposition of Graphs into (g, f)-Factors

Let G be a multigraph, g and f be integer-valued functions defined on V(G). Then a graph G is called a (g, f)-graph if g(x)≤deg _G(x)≤f(x) for each x∈V(G), and a (g, f)-factor is a spanning (g, f)-subgraph. If the edges of graph G can be decomposed into (g, f)-factors, then we say that G is (g, f)-factorable. In this paper, we obtained some sufficient conditions for a graph to be (g, f)-factorable. One of them is the following: Let m be a positive integer, l be an integer with l=m (mod 4) and 0≤l≤3. If G is an -graph, then G is (g, f)-factorable. Our results imply several previous (g, f)-factorization results. Revised: June 11, 1998     

Binding number and Hamiltonian(g, f)-factors in graphs

A(g, f)-factorF of a graphG is called a Hamiltonian(g, f)-factor ifF contains a Hamiltonian cycle. The binding number ofG is defined by $bind(G) = \min \left\{ {\frac{{|N_G (X)|}}{{|X|}}|\not 0 \ne X \subset V(G), N_G (X) \ne V(G)} \right\}$ . Let G be a connected graph, and let a andb be integers such that 4 ≤ a <b. Letg, f be positive integer-valued functions defined onV(G) such that a ≤g(x) < f(x) ≤ b for everyx ∈V(G). In this paper, it is proved that if $bind(G) \geqslant \frac{{(a + b - 5)(n - 1)}}{{(a - 2)n - 3(a + b - 5)}}, \nu (G) \geqslant \frac{{(a + b - 5)^2 }}{{a - 2}}$ and for any nonempty independent subset X ofV(G), thenG has a Hamiltonian(g, f)-factor.     

Linear independence of time-frequency shifts under a generalized Schrödinger representation

Let r_\mathbbR \rho_{\mathbb{R}} be the classical Schrödinger representation of the Heisenberg group and let L \Lambda be a finite subset of \mathbbR ×\mathbbR \mathbb{R} \times \mathbb{R} . The question of when the set of functions {t ? e^{2 pi y t} f(t + x) = (r_\mathbbR(x, y, 1) f)(t) : (x, y) ? L} \{t \mapsto e^{2 \pi i y t} f(t + x) = (\rho_{\mathbb{R}}(x, y, 1) f)(t) : (x, y) \in \Lambda\} is linearly independent for all f ? L²(\mathbbR), f 1 0 f \in L^2(\mathbb{R}), f \neq 0 , arises from Gabor analysis. We investigate an analogous problem for locally compact abelian groups G. For a finite subset L \Lambda of G ×[^(G)] G \times \widehat{G} and r_G \rho_G the Schrödinger representation of the Heisenberg group associated with G, we give a necessary and in many situations also sufficient condition for the set {r_G (x, w, 1)f : (x, w) ? L} \{\rho_G (x, w, 1)f : (x, w) \in \Lambda\} to be linearly independent for all f ? L²(G), f 1 0 f \in L^2(G), f \neq 0 .     

On Group Choosability of Graphs,II

Given a group A and a directed graph G, let F(G, A) denote the set of all maps ${f : E(G) \rightarrow A}$ . Fix an orientation of G and a list assignment ${L : V(G) \mapsto 2^A}$ . For an ${f \in F(G, A)}$ , G is (A, L, f)-colorable if there exists a map ${c:V(G) \mapsto \cup_{v \in V(G)}L(v)}$ such that ${c(v) \in L(v)}$ , ${\forall v \in V(G)}$ and ${c(x)-c(y)\neq f(xy)}$ for every edge e = xy directed from x to y. If for any ${f\in F(G,A)}$ , G has an (A, L, f)-coloring, then G is (A, L)-colorable. If G is (A, L)-colorable for any group A of order at least k and for any k-list assignment ${L:V(G) \rightarrow 2^A}$ , then G is k-group choosable. The group choice number, denoted by ${\chi_{gl}(G)}$ , is the minimum k such that G is k-group choosable. In this paper, we prove that every planar graph is 5-group choosable, and every planar graph with girth at least 5 is 3-group choosable. We also consider extensions of these results to graphs that do not have a K ₅ or a K _3,3 as a minor, and discuss group choosability versions of Hadwiger’s and Woodall’s conjectures.     

Induced Cycles in Graphs

The maximum number vertices of a graph G inducing a 2-regular subgraph of G is denoted by \(c_\mathrm{ind}(G)\). We prove that if G is an r-regular graph of order n, then \(c_\mathrm{ind}(G) \ge \frac{n}{2(r-1)} + \frac{1}{(r-1)(r-2)}\) and we prove that if G is a cubic, claw-free graph on order n, then \(c_\mathrm{ind}(G) > \frac{13}{20}n\) and this bound is asymptotically best possible.     

On solvability of derivative dependent doubly singular boundary value problems

In this paper we establish existence of solutions of singular boundary value problem ?(p(x)y ^′(x))^′=q(x)f(x,y,py′) for 0<x≤b and $\lim_{x\rightarrow0^{+}}p(x)y^{\prime}(x)=0$ , α ₁ y(b)+β ₁ p(b)y ^′(b)=γ ₁ with p(0)=0 and q(x) is allowed to have integrable discontinuity at x=0. So the problem may be doubly singular. Here we consider $\lim_{x\rightarrow0^{+}}\frac{q(x)}{p'(x)}\neq0$ therefore $\lim_{x\rightarrow0^{+}}p(x)y'(x)=0$ does not imply y′(0)=0 unless $\lim_{x\rightarrow0^{+}}f(x,y(x),p(x)y'(x))=0$ .     

The upper connected geodetic number and forcing connected geodetic number of a graph

For a connected graph G of order p≥2, a set S⊆V(G) is a geodetic set of G if each vertex v∈V(G) lies on an x-y geodesic for some elements x and y in S. The minimum cardinality of a geodetic set of G is defined as the geodetic number of G, denoted by g(G). A geodetic set of cardinality g(G) is called a g-set of G. A connected geodetic set of G is a geodetic set S such that the subgraph G[S] induced by S is connected. The minimum cardinality of a connected geodetic set of G is the connected geodetic number of G and is denoted by g_c(G). A connected geodetic set of cardinality g_c(G) is called a g_c-set of G. A connected geodetic set S in a connected graph G is called a minimal connected geodetic set if no proper subset of S is a connected geodetic set of G. The upper connected geodetic number is the maximum cardinality of a minimal connected geodetic set of G. We determine bounds for and determine the same for some special classes of graphs. For positive integers r,d and n≥d+1 with r≤d≤2r, there exists a connected graph G with , and . Also, for any positive integers 2≤a<b≤c, there exists a connected graph G such that g(G)=a, g_c(G)=b and . A subset T of a g_c-set S is called a forcing subset for S if S is the unique g_c-set containing T. A forcing subset for S of minimum cardinality is a minimum forcing subset of S. The forcing connected geodetic number of S, denoted by f_c(S), is the cardinality of a minimum forcing subset of S. The forcing connected geodetic number of G, denoted by f_c(G), is f_c(G)=min{f_c(S)}, where the minimum is taken over all g_c-sets S in G. It is shown that for every pair a,b of integers with 0≤a≤b−4, there exists a connected graph G such that f_c(G)=a and g_c(G)=b.     

Eigenvalues and homology of flag complexes and vector representations of graphs

The flag complex of a graph G = (V, E) is the simplicial complex X(G) on the vertex set V whose simplices are subsets of V which span complete subgraphs of G. We study relations between the first eigenvalues of successive higher Laplacians of X(G). One consequence is the following:Theorem: Let λ₂(G) denote the second smallest eigenvalue of the Laplacian of G. If \,\frac{k}{k+1}|V|$$" align="middle" border="0"> then Applications include a lower bound on the homological connectivity of the independent sets complex I(G), in terms of a new graph domination parameter Γ(G) defined via certain vector representations of G. This in turns implies Hall type theorems for systems of disjoint representatives in hypergraphs.Received: January 2004 Revised: August 2004 Accepted: August 2004