Extremal trees with given degree sequence for the Randić index

The Randi? index of a graph G is the sum of $((d(u))(d(v)){)}^{\alpha }$ over all edges $\mathit{uv}$ of G, where $d(v)$ denotes the degree of $v$ in G, $\alpha \ne 0$. When $\alpha =1$, it is the weight of a graph. Delorme, Favaron, and Rautenbach characterized the trees with a given degree sequence with maximum weight, where the question of finding the tree that minimizes the weight is left open. In this note, we characterize the extremal trees with given degree sequence for the Randi? index, thus answering the same question for weight. We also provide an algorithm to construct such trees.     

Degree sequence conditions for maximally edge-connected and super-edge-connected digraphs depending on the clique number

Let $D$ be a finite and simple digraph with vertex set $V\left(D\right)$. For a vertex $v\in V\left(D\right)$, the degree $d\left(v\right)$ of $v$ is defined as the minimum value of its out-degree $d^{+}\left(v\right)$ and its in-degree $d^{?}\left(v\right)$. If $D$ is a graph or a digraph with minimum degree $\delta$ and edge-connectivity $\lambda$, then $\lambda \le \delta$. A graph or a digraph is maximally edge-connected if $\lambda =\delta$. A graph or a digraph is called super-edge-connected if every minimum edge-cut consists of edges adjacent to or from a vertex of minimum degree.In this note we present degree sequence conditions for maximally edge-connected and super-edge-connected digraphs depending on the clique number of the underlying graph.     

Fuzzy Perfect Mappings and Q-Compactness in Smooth Fuzzy Topological Spaces

We point out that the product of two fuzzy closed sets of smooth fuzzy topological spaces need not be fuzzy closed with respect to the the existing notion of product smooth fuzzy topology. To get this property, we introduce a new suitable product smooth fuzzy topology. We investigate whether $F_1\times F_2$ and $(F,H)$ are weakly smooth fuzzy continuity whenever $F_1$, $F_2$, $F$ and $H$ are weakly smooth fuzzy continuous. Using this new product smooth fuzzy topology, we define smooth fuzzy perfect mapping and prove that composition of two smooth fuzzy perfect mappings is smooth fuzzy perfect under some additional conditions. We also introduce two new notions of compactness called $Q$-compactness and $Q$-$\alpha$-compactness; and discuss the compactness of the image of a $Q$-compact set ($Q$-$\alpha$-compact set) under a weakly smooth fuzzy continuous function ($(\alpha ,\beta )$-weakly smooth fuzzy continuous function).     

Degree Conditions and Degree Bounded Trees

In this paper, we give sufficient conditions for a graph to have degree bounded trees. Let G be a connected graph and $A\subseteq V(G)$. We denote by ${\sigma }_k(A)$ the minimum value of the degree sum in G of any k pairwise nonadjacent vertices of A, and by $w(G-A)$ the number of components of the subgraph $G-A$ of G induced by $V(G)-A$. Our main results are the following: (i) If ${\sigma }_k(A)⩾|G|-1$, then G contains a tree T with maximum degree ⩽k and $A\subseteq V(T)$. (ii) If ${\sigma }_{k-w(G-A)}(A)⩾|A|-1$, then G contains a spanning tree T with $d_T(x)⩽k$ for any $x\in A$. These are generalizations of the result by S. Win [S. Win, Existenz von Gerüsten mit Vorgeschriebenem Maximalgrad in Graphen, Abh. Math. Seminar Univ. Humburg 43 (1975) 263–267] and degree conditions are sharp.     

List r-hued chromatic number of graphs with bounded maximum average degrees

For integers $k,r>0$, a $(k,r)$-coloring of a graph $G$ is a proper coloring $c$ with at most $k$ colors such that for any vertex $v$ with degree $d\left(v\right)$, there are at least min$\{d\left(v\right),r\}$ different colors present at the neighborhood of $v$. The $r$-hued chromatic number of $G$, ${\chi }_r\left(G\right)$, is the least integer $k$ such that a $(k,r)$-coloring of $G$ exists. The list$r$-hued chromatic number${\chi }_{L,r}\left(G\right)$ of $G$ is similarly defined. Thus if $\Delta \left(G\right)\ge r$, then ${\chi }_{L,r}\left(G\right)\ge {\chi }_r\left(G\right)\ge r+1$. We present examples to show that, for any sufficiently large integer $r$, there exist graphs with maximum average degree less than 3 that cannot be $(r+1,r)$-colored. We prove that, for any fraction $q<\frac{14}{5}$, there exists an integer $R=R\left(q\right)$ such that for each $r\ge R$, every graph $G$ with maximum average degree $q$ is list $(r+1,r)$-colorable. We present examples to show that for some $r$ there exist graphs with maximum average degree less than 4 that cannot be $r$-hued colored with less than $\frac{3r}{2}$ colors. We prove that, for any sufficiently small real number $?>0$, there exists an integer $h=h\left(?\right)$ such that every graph $G$ with maximum average degree $4??$ satisfies ${\chi }_{L,r}\left(G\right)\le r+h\left(?\right)$. These results extend former results in Bonamy et al. (2014).     

Lehmer's totient problem over Fq[x]

In this paper, we consider the function field analogue of the Lehmer's totient problem. Let $p(x)\in {\mathbb{F}}_q[x]$ and $\phi (q,p(x))$ be the Euler's totient function of $p(x)$ over ${\mathbb{F}}_q[x]$, where ${\mathbb{F}}_q$ is a finite field with q elements. We prove that $\phi (q,p(x))|(q^{\mathrm{deg}(p(x))}?1)$ if and only if (i) $p(x)$ is irreducible; or (ii) $q=3$, $p(x)$ is the product of any 2 non-associate irreducibles of degree 1; or (iii) $q=2$, $p(x)$ is the product of all irreducibles of degree 1, all irreducibles of degree 1 and 2, and the product of any 3 irreducibles one each of degree 1, 2 and 3.     

On a conjecture of the Randić index and the minimum degree of graphs

The Randi? index $R\left(G\right)$ of a graph $G$ is defined by $R\left(G\right)={\sum }_{uv}\frac{1}{\sqrt{d\left(u\right)d\left(v\right)}}$, where $d\left(u\right)$ is the degree of a vertex $u$ and the summation extends over all edges $uv$ of $G$. Delorme et al. (2002)  [6] put forward a conjecture concerning the minimum Randi? index among all$n$-vertex connected graphs with the minimum degree at least $k$. In this work, we show that the conjecture is true given the graph contains $k$ vertices of degree $n?1$. Further, it is true among $k$-trees.     

Codes defined by forms of degree 2 on Hermitian surfaces and Sørensen's conjecture

We study the functional codes $C_h(X)$ defined by Lachaud in [G. Lachaud, Number of points of plane sections and linear codes defined on algebraic varieties, in: Arithmetic, Geometry, and Coding Theory, Luminy, France, 1993, de Gruyter, Berlin, 1996, pp. 77–104] where $X\subset {\mathbb{P}}^N$ is an algebraic projective variety of degree d and dimension m. When X is a Hermitian surface in $\mathit{PG}(3,q)$, Sørensen in [A.B. Sørensen, Rational points on hypersurfaces, Reed–Muller codes and algebraic-geometric codes, PhD thesis, Aarhus, Denmark, 1991], has conjectured for $h⩽t$ (where $q=t^2$) the following result:$\mathrm{\#}{X}_{Z(f)}({\mathbb{F}}_q)⩽h(t^3+t^2-t)+t+1$ which should give the exact value of the minimum distance of the functional code $C_h(X)$. In this paper we resolve the conjecture of Sørensen in the case of quadrics (i.e. $h=2$), we show the geometrical structure of the minimum weight codewords and their number; we also estimate the second weight and the geometrical structure of the codewords reaching this second weight.     

A panconnectivity theorem for bipartite graphs

Let $G$ be a simple $m\times n$ bipartite graph with $m\ge n$. We prove that if the minimum degree of $G$ satisfies $\delta \left(G\right)\ge m∕2+1$, then $G$ is bipanconnected: for every pair of vertices $x,y$, and for every appropriate integer $2\le ?\le 2n$, there is an $x,y$-path of length $?$ in $G$.     

Homomorphism complexes and k-cores

For any fixed graph $G$, we prove that the topological connectivity of the graph homomorphism complex Hom($G,K_m$) is at least $m?D\left(G\right)?2$, where $D\left(G\right)={max}_{H?G}\delta \left(H\right)$, for $\delta \left(H\right)$ the minimum degree of a vertex in a subgraph $H$. This generalizes a theorem of C?uki? and Kozlov, in which the maximum degree $\Delta \left(G\right)$ was used in place of $D\left(G\right)$, and provides a high-dimensional analogue of the graph theoretic bound for chromatic number, $\chi \left(G\right)\le D\left(G\right)+1$, as $\chi \left(G\right)=min\{m:\text{Hom}(G,K_m)\ne ?\}$. Furthermore, we use this result to examine homological phase transitions in the random polyhedral complexes Hom$(G(n,p),K_m)$ when $p=c∕n$ for a fixed constant $c>0$.     

Dynamic Aggregation Operators Based on Intuitionistic Fuzzy Tools and Einstein Operations

The idea of combine aggregation and intuitionistic fuzzy information plays essential role in multi criteria decision making (MCDM) process. However, this new branch has attracted researchers that study in different fields recently. In this paper, we study MCDM problems with intuitionistic fuzzy environment. Firstly, we introduce some operations related with Einstein t-norm and t-conorm such as, Einstein sum, product and exponentiation. After that, we define dynamic intuitionistic fuzzy Einstein averaging (DIFWA${}^{?}$) operator and dynamic intuitionistic fuzzy Einstein geometric averaging (DIFWG${}^{?}$) operator. Their notable property is that collect and aggregate values in different period based on Einstein operations in intuitionistic fuzzy set (IFS)s. In addition, we compare the defined operators with the existing intuitionistic fuzzy dynamic operators and get the corresponding relations. We establish two methods using with DIFWA${}^{?}$ and DIFWG${}^{?}$ to solve MCDM problems with intuitionistic fuzzy tools. Finally, an illustrated example is presented to show the applicability of the introduced methods.     

Starlike trees whose maximum degree exceed 4 are determined by their Q-spectra

Let $A(G)$ and $D(G)$ be the adjacency matrix and the degree matrix of a graph $G$, respectively. The matrix $D(G)+A(G)$ is called the signless Laplacian matrix of $G$. The spectrum of the matrix $D(G)+A(G)$ is called the Q-spectrum of $G$. A graph is said to be determined by its Q-spectrum if there is no other non-isomorphic graph with the same Q-spectrum. In this paper, we prove that all starlike trees whose maximum degree exceed $4$ are determined by their Q-spectra.     

On partitions of K2,3-free graphs under degree constraints

Suppose that $s$, $t$ are two positive integers, and $?$ is a set of graphs. Let $g(s,t;?)$ be the least integer $g$ such that any $?$-free graph with minimum degree at least $g$ can be partitioned into two sets which induced subgraphs have minimum degree at least $s$ and $t$, respectively. For a given graph $H$, we simply write $g(s,t;H)$ for $g(s,t;?)$ when $?=\left\{H\right\}$. In this paper, we show that if $s,t\ge 2$, then $g(s,t;K_{2,3})\le s+t$ and $g(s,t;\{K_3,C_8,K_{2,3}\})\le s+t?1$. Moreover, if $?$ is the set of graphs obtained by connecting a single vertex to exactly two vertices of $K_4?e$, then $g(s,t;?)\le s+t$ on $?$-free graphs with at least five vertices, which generalize a result of Liu and Xu (2017).