اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدWord-representability of Toeplitz graphs
57
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Distinct letters $x$ and $y$ alternate in a word $w$ if after deleting in $w$ all letters but the copies of $x$ and $y$ we either obtain a word of the form $xyxycdots$ (of even or odd length) or a word of the form $yxyxcdots$ (of even or odd length). A graph $G=(V,E)$ is word-representable if there exists a word $w$ over the alphabet $V$ such that letters $x$ and $y$ alternate in $w$ if and only if $xy$ is an edge in $E$. In this paper we initiate the study of word-representable Toeplitz graphs, which are Riordan graphs of the Appell type. We prove that several general classes of Toeplitz graphs are word-representable, and we also provide a way to construct non-word-representable Toeplitz graphs. Our work not only merges the theories of Riordan matrices and word-representable graphs via the notion of a Riordan graph, but also it provides the first systematic study of word-representability of graphs defined via patterns in adjacency matrices. Moreover, our paper introduces the notion of an infinite word-representable Riordan graph and gives several general examples of such graphs. It is the first time in the literature when the word-representability of infinite graphs is discussed.
قيم البحث
اقرأ أيضاً
A graph $G=(V,E)$ is word-representable if there exists a word $w$ over the alphabet $V$ such that letters $x$ and $y$, $x eq y$, alternate in $w$ if and only if $(x,y)in E$. Halld{o}rsson et al. have shown that a graph is word-representable if and o
nly if it admits a so-called semi-transitive orientation. A corollary to this result is that any 3-colorable graph is word-representable. Akrobotu et al. have shown that a triangulation of a grid graph is word-representable if and only if it is 3-colorable. This result does not hold for triangulations of grid-covered cylinder graphs, namely, there are such word-representable graphs with chromatic number 4. In this paper we show that word-representability of triangulations of grid-covered cylinder graphs with three sectors (resp., more than three sectors) is characterized by avoiding a certain set of six minimal induced subgraphs (resp., wheel graphs $W_5$ and $W_7$).
Let $X$ be a simplicial complex on vertex set $V$. We say that $X$ is $d$-representable if it is isomorphic to the nerve of a family of convex sets in $mathbb{R}^d$. We define the $d$-boxicity of $X$ as the minimal $k$ such that $X$ can be written as
the intersection of $k$ $d$-representable simplicial complexes. This generalizes the notion of boxicity of a graph, defined by Roberts. A missing face of $X$ is a set $tausubset V$ such that $tau otin X$ but $sigmain X$ for any $sigmasubsetneq tau$. We prove that the $d$-boxicity of a simplicial complex on $n$ vertices without missing faces of dimension larger than $d$ is at most $leftlfloorfrac{1}{d+1}binom{n}{d}rightrfloor$. The bound is sharp: the $d$-boxicity of a simplicial complex whose set of missing faces form a Steiner $(d,d+1,n)$-system is exactly $frac{1}{d+1}binom{n}{d}$.
For an integer $n>2$, a rank-$n$ matroid is called an $n$-spike if it consists of $n$ three-point lines through a common point such that, for all $kin{1, 2, ..., n - 1}$, the union of every set of $k$ of these lines has rank $k+1$. Spikes are very sp
ecial and important in matroid theory. In 2003 Wu found the exact numbers of $n$-spikes over fields with 2, 3, 4, 5, 7 elements, and the asymptotic values for larger finite fields. In this paper, we prove that, for each prime number $p$, a $GF(p$) representable $n$-spike $M$ is only representable on fields with characteristic $p$ provided that $n ge 2p-1$. Moreover, $M$ is uniquely representable over $GF(p)$.
The notion of a 12-representable graph was introduced by Jones et al.. This notion generalizes the notions of the much studied permutation graphs and co-interval graphs. It is known that any 12-representable graph is a comparability graph, and also t
hat a tree is 12-representable if and only if it is a double caterpillar. Moreover, Jones et al. initiated the study of 12-representability of induced subgraphs of a grid graph, and asked whether it is possible to characterize such graphs. This question in is meant to be about induced subgraphs of a grid graph that consist of squares, which we call square grid graphs. However, an induced subgraph in a grid graph does not have to contain entire squares, and we call such graphs line grid graphs. In this paper we answer the question of Jones et al. by providing a complete characterization of $12$-representable square grid graphs in terms of forbidden induced subgraphs. Moreover, we conjecture such a characterization for the line grid graphs and give a number of results towards solving this challenging conjecture. Our results are a major step in the direction of characterization of all 12-representable graphs since beyond our characterization, we also discuss relations between graph labelings and 12-representability, one of the key open questions in the area.
We confirm the equitable $Delta$-coloring conjecture for interval graphs and establish the monotonicity of equitable colorability for them. We further obtain results on equitable colorability about square (or Cartesian) and cross (or direct) products of graphs.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
